ARC173-B Make Many Triangles

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("7");
            WillReturn.Add("0 0");
            WillReturn.Add("1 1");
            WillReturn.Add("0 3");
            WillReturn.Add("5 2");
            WillReturn.Add("3 4");
            WillReturn.Add("2 0");
            WillReturn.Add("2 2");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("0 0");
            WillReturn.Add("0 1000000000");
            WillReturn.Add("0 -1000000000");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("300");
            for (int I = 1; I <= 300; I++) {
                WillReturn.Add(string.Format("{0} {1}", I, I % 100));
            }
        }

        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PointDef
    {
        internal long X;
        internal long Y;
    }
    static List<PointDef> mPointList = new List<PointDef>();

    static long mN;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        List<string> InputList = GetInputList();

        mN = long.Parse(InputList[0]);
        if (mN <= 2) {
            Console.WriteLine(0);
            return;
        }

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            mPointList.Add(WillAdd);
        }

        int Answer = 0;
        while (true) {
            Answer = Math.Max(Answer, RandTest());
            if (sw.ElapsedMilliseconds >= 1900) { // 1.9秒続ける
                break;
            }
        }
        Console.WriteLine(Answer);
    }

    static int RandTest()
    {
        int UB = mPointList.Count - 1;

        mPointList = mPointList.OrderBy(pX => Guid.NewGuid()).ToList();
        var RemoveSet = new HashSet<int>();
        for (int I = 0; I <= UB; I++) {
            if (RemoveSet.Contains(I)) continue;
            bool WillBreak2 = false;
            for (int J = I + 1; J <= UB; J++) {
                if (RemoveSet.Contains(J)) continue;
                PointDef StaPos;
                StaPos.X = mPointList[I].X;
                StaPos.Y = mPointList[I].Y;

                PointDef Vector;
                Vector.X = mPointList[J].X - mPointList[I].X;
                Vector.Y = mPointList[J].Y - mPointList[I].Y;
                ExecVectorDiv(ref Vector);
                for (int K = J + 1; K <= UB; K++) {
                    if (RemoveSet.Contains(K)) continue;
                    PointDef Sahen;
                    Sahen.X = mPointList[K].X - StaPos.X;
                    Sahen.Y = mPointList[K].Y - StaPos.Y;

                    if (Sahen.X * Vector.Y == Sahen.Y * Vector.X) {
                        continue;
                    }
                    RemoveSet.Add(I);
                    RemoveSet.Add(J);
                    RemoveSet.Add(K);
                    WillBreak2 = true;
                    break;
                }
                if (WillBreak2) break;
            }
        }
        return RemoveSet.Count / 3;
    }

    // ユークリッドの互除法で2数の最大公約数を求める
    static long DeriveGCD(long pVal1, long pVal2)
    {
        long WarareruKazu = pVal2;
        long WaruKazu = pVal1;

        while (true) {
            long Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }

    // 2次元ベクトルの各成分を、GCD(X成分,Y成分)で割る
    // X成分が0なら、Y成分を符号にする
    // Y成分が0なら、X成分を符号にする
    static void ExecVectorDiv(ref PointDef pVect)
    {
        if (pVect.X == 0) {
            pVect.Y = Math.Sign(pVect.Y);
        }
        else if (pVect.Y == 0) {
            pVect.X = Math.Sign(pVect.X);
        }
        else {
            long GCD = DeriveGCD(Math.Abs(pVect.X), Math.Abs(pVect.Y));
            pVect.X /= GCD;
            pVect.Y /= GCD;
        }
    }
}

解説

「ランダムな優先順位で、1直線上にない3点を、貪欲に選ぶ」ことを繰り返す
のを1.9秒間繰り返し、
最良値を解とする、モンテカルロ法を使ってます。