AtCoderのPAST    次のPASTの問題へ    前のPASTの問題へ

第10回PAST I 対称変換


問題へのリンク


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

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

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

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

        var SList = new List<PointDef>();
        var TList = 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];
            SList.Add(WillAdd);
        }

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

        // 十分条件01 対称移動しなくても全ての点が一致
        bool IsSame = true;
        SList = SList.OrderBy(pX => pX.X).ThenBy(pX => pX.Y).ToList();
        TList = TList.OrderBy(pX => pX.X).ThenBy(pX => pX.Y).ToList();
        for (int I = 0; I <= SList.Count - 1; I++) {
            if (SList[I].X != TList[I].X) IsSame = false;
            if (SList[I].Y != TList[I].Y) IsSame = false;
        }
        if (IsSame) {
            Console.WriteLine("Yes");
            return;
        }

        // 十分条件02 Y座標の中点が全て等しい
        bool Sufficient02 = true;
        SList = SList.OrderBy(pX => pX.X).ThenBy(pX => pX.Y).ToList();
        TList = TList.OrderBy(pX => pX.X).ThenByDescending(pX => pX.Y).ToList();
        var YMidSet = new HashSet<decimal>();
        for (int I = 0; I <= SList.Count - 1; I++) {
            if (SList[I].X != TList[I].X) {
                Sufficient02 = false;
                break;
            }
            decimal Mid = (decimal)(SList[I].Y + TList[I].Y) / 2;
            YMidSet.Add(Mid);
        }
        if (YMidSet.Count > 1) Sufficient02 = false;

        // 十分条件03 X座標の中点が全て等しい
        bool Sufficient03 = true;
        SList = SList.OrderBy(pX => pX.Y).ThenBy(pX => pX.X).ToList();
        TList = TList.OrderBy(pX => pX.Y).ThenByDescending(pX => pX.X).ToList();
        var XMidSet = new HashSet<decimal>();
        for (int I = 0; I <= SList.Count - 1; I++) {
            if (SList[I].Y != TList[I].Y) {
                Sufficient03 = false;
                break;
            }
            decimal Mid = (decimal)(SList[I].X + TList[I].X) / 2;
            XMidSet.Add(Mid);
        }
        if (XMidSet.Count > 1) Sufficient03 = false;

        if (Sufficient02 || Sufficient03) {
            Console.WriteLine("Yes");
        }
        else {
            Console.WriteLine("No");
        }
    }
}


解説

最初から全ての点が一致してる場合。
X座標ごとに分類して、Y座標の中点が1つしかない場合。
Y座標ごとに分類して、X座標の中点が1つしかない場合。

の3通りの、少なくとも1つの場合を満たすかをチェックしてます。