ABC248-E K-colinear Line

問題へのリンク

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("5 2");
            WillReturn.Add("0 0");
            WillReturn.Add("1 0");
            WillReturn.Add("0 1");
            WillReturn.Add("-1 0");
            WillReturn.Add("0 -1");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1");
            WillReturn.Add("0 0");
            //Infinity
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PointDef
    {
        internal long X;
        internal long Y;
    }

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

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

        SplitAct(InputList[0]);
        long K = wkArr[1];

        if (K == 1) {
            Console.WriteLine("Infinity");
            return;
        }

        var PointList = new List<PointDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            PointList.Add(WillAdd);
        }
        PointList = PointList.OrderBy(pX => pX.X).ToList();

        long Answer = 0;
        long UB = PointList.Count - 1;
        for (int I = 0; I <= UB; I++) {
            for (int J = I + 1; J <= UB; J++) {
                PointDef StaPos;
                StaPos.X = PointList[I].X;
                StaPos.Y = PointList[I].Y;

                PointDef Vector;
                Vector.X = PointList[J].X - PointList[I].X;
                Vector.Y = PointList[J].Y - PointList[I].Y;
                ExecVectorDiv(ref Vector);

                // 直線ごとに通る点をカウント
                long MatchCnt = 0;
                for (int L = 0; L <= UB; L++) {
                    PointDef Sahen;
                    Sahen.X = PointList[L].X - StaPos.X;
                    Sahen.Y = PointList[L].Y - StaPos.Y;

                    if (Sahen.X * Vector.Y == Sahen.Y * Vector.X) {
                        // 最初の2点は、必ず、先頭2件を選ぶようにする
                        if (L < I) break; // 0番目の点は、1番左であること
                        if (I < L && L < J) break; // 0番目の点と1番目の点の間に、点がないこと

                        MatchCnt++;
                        if (MatchCnt >= K) {
                            Answer++;
                            break;
                        }
                    }
                }
            }
        }
        Console.WriteLine(Answer);
    }

    // ユークリッドの互除法で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;
        }
    }
}

解説

直線ごとに通る点をカウントしてます。

2点が決まれば、直線が決まって、
任意の3点目を通るかの判定は、

(開始X,開始Y) + 定数(変位ベクトルのX , 変位ベクトルのY) = (終了X,終了Y)
移行して、
(終了X - 開始X, 終了Y - 開始Y) = 定数(変位ベクトルのX , 変位ベクトルのY)
で、
比の一致になるので、内項と外項の積が等しいかを見れば良く、
A:B=C:D ⇔ BC = AD
を使って判定できます。

数える直線の重複防止で
最初の2点は、必ず、先頭2件を選ぶようにしてます。
これは、下記の一直線上の点を書いた上で
●  ●  ●  ●  ●
0番目の点は、1番左であること
0番目の点と1番目の点の間に、点がないこと
という条件で判定できると分かります。