AtCoderのABC    次のABCの問題へ    前のABCの問題へ

ABC207-D Congruence Points


問題へのリンク


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

    const double EPS = 0.01D;

    struct PointDef
    {
        internal double X;
        internal double Y;
    }
    static HashSet<string> mABPointHashSet = new HashSet<string>();

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

        double N = double.Parse(InputList[0]);

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

        var ABPointList = new List<PointDef>();
        var CDPointList = new List<PointDef>();

        foreach (string EachStr in InputList.Skip(1).Take((int)N)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            ABPointList.Add(WillAdd);
        }
        foreach (string EachStr in InputList.Skip(1 + (int)N)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            CDPointList.Add(WillAdd);
        }

        // 原点を1つめの座標で固定して、全ての点を原点に平行移動
        PointDef Genten = new PointDef() { X = 0, Y = 0 };
        PointDef DiffVector1 = SetVector(ABPointList[0], Genten);
        for (int I = 0; I <= ABPointList.Count - 1; I++) {
            PointDef NewPoint = ABPointList[I];
            NewPoint.X += DiffVector1.X;
            NewPoint.Y += DiffVector1.Y;
            ABPointList[I] = NewPoint;
        }

        foreach (PointDef EachPoint in ABPointList) {
            string Hash = GetHash(EachPoint.X, EachPoint.Y);
            mABPointHashSet.Add(Hash);
        }

        // 全ての点を原点にして、平行移動し、回転で一致できるかを試す
        for (int I = 0; I <= CDPointList.Count - 1; I++) {
            PointDef DiffVector2 = SetVector(CDPointList[I], Genten);
            var NewCDPointList = new List<PointDef>();
            for (int J = 0; J <= CDPointList.Count - 1; J++) {
                PointDef NewPoint;
                NewPoint.X = CDPointList[J].X + DiffVector2.X;
                NewPoint.Y = CDPointList[J].Y + DiffVector2.Y;
                NewCDPointList.Add(NewPoint);
            }
            if (IsKaitenMatch(NewCDPointList)) {
                Console.WriteLine("Yes");
                return;
            }
        }
        Console.WriteLine("No");
    }

    static string GetHash(double pX, double pY)
    {
        return string.Format("{0},{1}", pX, pY);
    }

    // 座標のListを引数として、回転で一致できるかを返す
    static bool IsKaitenMatch(List<PointDef> pCDPointList)
    {
        // 回転する角度でループ
        for (double LoopKakudo = 0; LoopKakudo <= 360; LoopKakudo += 0.05) {
            double rad = LoopKakudo * Math.PI / 180;
            double cos = Math.Cos(rad);
            double sin = Math.Sin(rad);

            // 全ての座標を回転させる
            var KaitenPosSet = new HashSet<string>();
            bool IsHuteki = false;
            foreach (PointDef EachPoint in pCDPointList) {
                PointDef ResultPos = Exec1JiHenkan(EachPoint, sin, cos);

                // 誤差を許容して格子点に丸める
                double RoundX = Math.Round(ResultPos.X);
                if (Math.Abs(ResultPos.X - RoundX) > EPS) {
                    IsHuteki = true;
                    break; // 不適が確定するのでbreak
                }
                double RoundY = Math.Round(ResultPos.Y);
                if (Math.Abs(ResultPos.Y - RoundY) > EPS) {
                    IsHuteki = true;
                    break; // 不適が確定するのでbreak
                }
                KaitenPosSet.Add(GetHash(RoundX, RoundY));
            }
            if (IsHuteki == false) {
                if (mABPointHashSet.SetEquals(KaitenPosSet)) {
                    return true;
                }
            }
        }
        return false;
    }

    // ベクトルとSinとCosを引数として、回転したベクトルを返す
    static PointDef Exec1JiHenkan(PointDef pPos, double pSin, double pCos)
    {
        PointDef WillReturn;
        WillReturn.X = pCos * pPos.X + pPos.Y * -pSin;
        WillReturn.Y = pSin * pPos.X + pPos.Y * pCos;
        return WillReturn;
    }

    // 始点と終点の座標を引数として、始点から終点へのベクトルを返す
    static PointDef SetVector(PointDef pStaPoint, PointDef pEndPoint)
    {
        PointDef WillReturn;
        WillReturn.X = pEndPoint.X - pStaPoint.X;
        WillReturn.Y = pEndPoint.Y - pStaPoint.Y;
        return WillReturn;
    }
}


解説

1個目の図形の原点は、1個目の点に固定して、平行移動させ、
2個目の図形の原点は、全ての点を試してます。

2個目の図形の回転は、0度から360度までを0.05度刻みとし、
格子点との許容誤差も、増減させてます。

1個目の図形と2個目の図形で同じ点の集合を持つかは、
HashSetクラスのSetEqualsメソッドで判定してます。