ABC255-B Light It Up

問題へのリンク

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("4 2");
            WillReturn.Add("2 3");
            WillReturn.Add("0 0");
            WillReturn.Add("0 1");
            WillReturn.Add("1 2");
            WillReturn.Add("2 0");
            //2.23606797749978969
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 1");
            WillReturn.Add("2");
            WillReturn.Add("-100000 -100000");
            WillReturn.Add("100000 100000");
            //282842.712474619009
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8 3");
            WillReturn.Add("2 6 8");
            WillReturn.Add("-17683 17993");
            WillReturn.Add("93038 47074");
            WillReturn.Add("58079 -57520");
            WillReturn.Add("-41515 -89802");
            WillReturn.Add("-72739 68805");
            WillReturn.Add("24324 -73073");
            WillReturn.Add("71049 72103");
            WillReturn.Add("47863 19268");
            //130379.280458974768
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

    static int[] mAArr;
    static List<PointDef> mPointList = new List<PointDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        mAArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

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

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

        double L = 0;
        double R = mPointList.Max(pX => pX.X * pX.X + pX.Y * pX.Y);

        while (L + 0.0000000001 < R) {
            double Mid = (L + R) / 2;

            if (CanAchieve(Mid)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        Console.WriteLine(R);
    }

    static bool CanAchieve(double pX)
    {
        var OKSet = new HashSet<int>();
        for (int I = 0; I <= mAArr.GetUpperBound(0); I++) {
            int Ind = mAArr[I] - 1;
            for (int J = 0; J <= mPointList.Count - 1; J++) {
                if (OKSet.Contains(J)) continue;

                long DiffX = mPointList[J].X - mPointList[Ind].X;
                long DiffY = mPointList[J].Y - mPointList[Ind].Y;

                long Norm = DiffX * DiffX + DiffY * DiffY;
                if (Norm <= pX * pX) {
                    OKSet.Add(J);
                }
            }
        }
        return OKSet.Count == mPointList.Count;
    }
}

解説

答えを二分探索してます。