ABC422-E Colinear

問題へのリンク

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("3");
            WillReturn.Add("1 1");
            WillReturn.Add("3 2");
            WillReturn.Add("2 4");
            //Yes
            //2 1 -8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("5 2");
            WillReturn.Add("1 3");
            WillReturn.Add("2 6");
            WillReturn.Add("4 4");
            WillReturn.Add("5 4");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11");
            WillReturn.Add("-9374372 85232388");
            WillReturn.Add("-60705467 86198234");
            WillReturn.Add("-7475320 80628487");
            WillReturn.Add("98066347 -23868213");
            WillReturn.Add("-12177678 85284287");
            WillReturn.Add("30535572 -35358356");
            WillReturn.Add("51324557 22410787");
            WillReturn.Add("28854279 44658587");
            WillReturn.Add("-28804873 82911971");
            WillReturn.Add("65052073 8819187");
            WillReturn.Add("-67744430 68365758");
            //Yes
            //4655800 4702358 -344340416016346
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

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

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

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

        var InsRandom = new Random();

        var sw = System.Diagnostics.Stopwatch.StartNew();

        int PointCnt = mPointList.Count;
        int UB = mPointList.Count - 1;
        while (true) {
            if (sw.ElapsedMilliseconds >= 1500) { // 1.5秒続ける
                Console.WriteLine("No");
                return;
            }

            int Ind1 = -1, Ind2 = -1;
            while (true) {
                Ind1 = InsRandom.Next(0, UB + 1);
                Ind2 = InsRandom.Next(0, UB + 1);
                if (Ind1 != Ind2) break;
            }

            long A, B, C;
            DeriveTyokusenABC(mPointList[Ind1].X, mPointList[Ind1].Y,
                              mPointList[Ind2].X, mPointList[Ind2].Y,
                              out A, out B, out C);

            int MatchCnt = 0;
            int UnMatchCnt = 0;
            foreach (PointDef EachPoint in mPointList) {
                if (A * EachPoint.X + B * EachPoint.Y + C == 0) {
                    if (PointCnt / 2 + 1 <= ++MatchCnt) {
                        Console.WriteLine("Yes");
                        Console.WriteLine("{0} {1} {2}", A, B, C);
                        return;
                    }
                }
                else {
                    // 枝切り
                    if (PointCnt / 2 + 1 <= ++UnMatchCnt) {
                        break;
                    }
                }
            }
        }
    }

    // (X1,Y1) , (X2,Y2) を引数とし、2点を通る直線の、aX + bY + c = 0 の (a,b,c)を設定
    static void DeriveTyokusenABC(long pX1, long pY1, long pX2, long pY2,
        out long pA, out long pB, out long pC)
    {
        long S = pX2 - pX1;
        long T = pY2 - pY1;
        pA = -T;
        pB = S;
        pC = T * pX1 - S * pY1;
    }
}

解説

条件を満たす直線の有無を1.5秒間調べてます。