ABC418-E Trapezium

問題へのリンク

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");
            WillReturn.Add("0 2");
            WillReturn.Add("0 5");
            WillReturn.Add("1 0");
            WillReturn.Add("2 1");
            WillReturn.Add("2 4");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8");
            WillReturn.Add("0 1");
            WillReturn.Add("1 3");
            WillReturn.Add("2 3");
            WillReturn.Add("3 1");
            WillReturn.Add("0 2");
            WillReturn.Add("1 0");
            WillReturn.Add("2 0");
            WillReturn.Add("3 2");
            //22
        }
        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);
        }

        int UB = mPointList.Count - 1;

        // 傾きの度数分布表
        var CntDict1 = new Dictionary<string, long>();

        // {傾き,長さ}の度数分布表
        var CntDict2 = new Dictionary<string, long>();

        for (int I = 0; I <= UB; I++) {
            for (int J = I + 1; J <= UB; J++) {
                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;
                long Norm = Vector.X * Vector.X + Vector.Y * Vector.Y;

                VectorGroupingTangent(ref Vector);

                string Hash1 = string.Format("{0},{1}", Vector.X, Vector.Y);
                if (CntDict1.ContainsKey(Hash1) == false) {
                    CntDict1[Hash1] = 0;
                }
                CntDict1[Hash1]++;

                string Hash2 = string.Format("{0},{1},{2}", Vector.X, Vector.Y, Norm);
                if (CntDict2.ContainsKey(Hash2) == false) {
                    CntDict2[Hash2] = 0;
                }
                CntDict2[Hash2]++;
            }
        }

        // 台形の数
        long Cnt1 = 0;
        foreach (var EachPair in CntDict1) {
            Cnt1 += (EachPair.Value) * (EachPair.Value - 1) / 2;
        }

        // 平行四辺形の数
        long Cnt2 = 0;
        foreach (var EachPair in CntDict2) {
            Cnt2 += (EachPair.Value) * (EachPair.Value - 1) / 2;
        }

        Console.WriteLine(Cnt1 - Cnt2 / 2);
    }

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

    // 変位ベクトルをタンジェントで同一化
    static void VectorGroupingTangent(ref PointDef pVect)
    {
        if (pVect.X == 0 && pVect.Y == 0) {
            return;
        }

        if (pVect.X == 0 && pVect.Y != 0) {
            pVect.Y = (pVect.Y == 0 ? 0 : 1);
            return;
        }

        if (pVect.X != 0 && pVect.Y == 0) {
            pVect.X = (pVect.X == 0 ? 0 : 1);
            return;
        }

        long GCD = DeriveGCD(Math.Abs(pVect.X), Math.Abs(pVect.Y));
        pVect.X /= GCD;
        pVect.Y /= GCD;

        // X成分は、プラスで統一
        if (pVect.X < 0) {
            pVect.X *= -1;
            pVect.Y *= -1;
        }
    }
}

解説

台形であることの必要十分条件として、
「1組の対辺が平行」という条件があります。

平行四辺形であることの必要十分条件として、
「1組の対辺が平行でその長さが等しい」という条件があります。

後は、
台形の個数と、平行四辺形の個数を求めて、
台形の個数 - 平行四辺形の個数
で解を求めてます。