AOJ 0524 星座探し

問題へのリンク

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("8 5");
            WillReturn.Add("6 4");
            WillReturn.Add("4 3");
            WillReturn.Add("7 10");
            WillReturn.Add("0 10");
            WillReturn.Add("10");
            WillReturn.Add("10 5");
            WillReturn.Add("2 7");
            WillReturn.Add("9 7");
            WillReturn.Add("8 10");
            WillReturn.Add("10 2");
            WillReturn.Add("1 2");
            WillReturn.Add("8 1");
            WillReturn.Add("6 7");
            WillReturn.Add("6 0");
            WillReturn.Add("0 9");
            WillReturn.Add("5");
            WillReturn.Add("904207 809784");
            WillReturn.Add("845370 244806");
            WillReturn.Add("499091 59863");
            WillReturn.Add("638406 182509");
            WillReturn.Add("435076 362268");
            WillReturn.Add("10");
            WillReturn.Add("757559 866424");
            WillReturn.Add("114810 239537");
            WillReturn.Add("519926 989458");
            WillReturn.Add("461089 424480");
            WillReturn.Add("674361 448440");
            WillReturn.Add("81851 150384");
            WillReturn.Add("459107 795405");
            WillReturn.Add("299682 6700");
            WillReturn.Add("254125 362183");
            WillReturn.Add("50795 541942");
            WillReturn.Add("0");
            //2 -3
            //-384281 179674
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PointDef
    {
        internal int X;
        internal int Y;
    }
    static List<PointDef> mSeizaPosList = new List<PointDef>();
    static List<PointDef> mSoraPosList = new List<PointDef>();

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

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

        int CurrInd = 0;
        while (true) {
            int M = int.Parse(InputList[CurrInd]);
            if (M == 0) break;

            mSeizaPosList.Clear();
            mSoraPosList.Clear();

            for (int I = CurrInd + 1; I <= CurrInd + 1 + M - 1; I++) {
                SplitAct(InputList[I]);
                PointDef WillAdd;
                WillAdd.X = wkArr[0];
                WillAdd.Y = wkArr[1];
                mSeizaPosList.Add(WillAdd);
            }

            int N = int.Parse(InputList[CurrInd + 1 + M]);
            for (int I = CurrInd + 1 + M + 1; I <= CurrInd + 1 + M + 1 + N - 1; I++) {
                SplitAct(InputList[I]);
                PointDef WillAdd;
                WillAdd.X = wkArr[0];
                WillAdd.Y = wkArr[1];
                mSoraPosList.Add(WillAdd);
            }

            Solve();

            CurrInd += 1 + M + 1 + N;
        }
    }

    static void Solve()
    {
        // 変位ベクトルのList
        var VectList = new List<PointDef>();
        for (int I = 1; I <= mSeizaPosList.Count - 1; I++) {
            PointDef WillAdd;
            WillAdd.X = mSeizaPosList[I].X - mSeizaPosList[0].X;
            WillAdd.Y = mSeizaPosList[I].Y - mSeizaPosList[0].Y;
            VectList.Add(WillAdd);
        }

        var SoraPosSet = new HashSet<string>();
        foreach (PointDef EachPoint in mSoraPosList) {
            string Hash = GetHash(EachPoint.X, EachPoint.Y);
            SoraPosSet.Add(Hash);
        }

        foreach (PointDef EachSoraPos in mSoraPosList) {
            bool IsOK = true;
            foreach (PointDef EachVect in VectList) {
                PointDef CheckPos;
                CheckPos.X = EachSoraPos.X + EachVect.X;
                CheckPos.Y = EachSoraPos.Y + EachVect.Y;
                string Hash = GetHash(CheckPos.X, CheckPos.Y);
                if (SoraPosSet.Contains(Hash) == false) {
                    IsOK = false;
                    break;
                }
            }
            if (IsOK) {
                int AnswerX = EachSoraPos.X - mSeizaPosList[0].X;
                int AnswerY = EachSoraPos.Y - mSeizaPosList[0].Y;
                Console.WriteLine("{0} {1}", AnswerX, AnswerY);
                return;
            }
        }
    }

    // 座標のハッシュ値を返す
    static string GetHash(long pX, long pY)
    {
        return string.Format("{0},{1}", pX, pY);
    }
}

解説

星座の0番目の座標が対応する、星空の座標の候補を全て調べてます。
チェックでは、変位ベクトルのListを使ってます。