ARC121-A 2nd Greatest Distance

問題へのリンク

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("1 2");
            WillReturn.Add("4 0");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("0 0");
            WillReturn.Add("0 0");
            WillReturn.Add("1 0");
            WillReturn.Add("0 1");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20");
            WillReturn.Add("407 361");
            WillReturn.Add("167 433");
            WillReturn.Add("756 388");
            WillReturn.Add("-551 -47");
            WillReturn.Add("306 -471");
            WillReturn.Add("36 928");
            WillReturn.Add("338 -355");
            WillReturn.Add("911 852");
            WillReturn.Add("288 70");
            WillReturn.Add("-961 -769");
            WillReturn.Add("-668 -386");
            WillReturn.Add("-690 -378");
            WillReturn.Add("182 -609");
            WillReturn.Add("-677 401");
            WillReturn.Add("-458 -112");
            WillReturn.Add("184 -131");
            WillReturn.Add("-243 888");
            WillReturn.Add("-163 471");
            WillReturn.Add("-11 997");
            WillReturn.Add("119 544");
            //1766
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct XYInfoDef
    {
        internal long ID;
        internal long X;
        internal long Y;
    }

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

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

        var XYInfoList = new List<XYInfoDef>();
        long CurrID = 1;
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYInfoDef WillAdd;
            WillAdd.ID = CurrID++;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            XYInfoList.Add(WillAdd);
        }

        var AnswerKouhoList = new List<long>();

        int UB = XYInfoList.Count - 1;

        var UsedHashSet = new HashSet<string>();
        Action<int, int> AddAct = (pInd1, pInd2) =>
        {
            string Hash = Gethash(XYInfoList[pInd1].ID, XYInfoList[pInd2].ID);
            if (UsedHashSet.Add(Hash) == false) return;

            long Kouho1 = Math.Abs(XYInfoList[pInd1].X - XYInfoList[pInd2].X);
            long Kouho2 = Math.Abs(XYInfoList[pInd1].Y - XYInfoList[pInd2].Y);
            AnswerKouhoList.Add(Math.Max(Kouho1, Kouho2));
        };

        // X座標でソートする
        XYInfoList.Sort((a, b) => a.X.CompareTo(b.X));
        AddAct(0, UB);
        AddAct(1, UB);
        AddAct(0, UB - 1);

        // Y座標でソートする
        XYInfoList.Sort((a, b) => a.Y.CompareTo(b.Y));
        AddAct(0, UB);
        AddAct(1, UB);
        AddAct(0, UB - 1);

        AnswerKouhoList = AnswerKouhoList.OrderByDescending(pX => pX).ToList();
        Console.WriteLine(AnswerKouhoList[1]);
    }

    // 座標の組み合わせのハッシュ値を求める
    static string Gethash(long pID1, long pID2)
    {
        long MinID = Math.Min(pID1, pID2);
        long MaxID = Math.Max(pID1, pID2);
        return string.Format("{0},{1}", MinID, MaxID);
    }
}

解説

X座標がMinと、X座標がMaxな座標のペア
X座標がSecondMinな座標と、X座標がMaxな座標のペア
X座標がMinな座標と、X座標がSecondMaxな座標のペア

などを候補として、チェビシェフ距離のSecondMaxを求めてます。
同じ座標のペアを使用しないように、座標ごとにIDを付与しておいて
座標のペアのハッシュ値も求めてます。