square869120コンテスト5 B問題 Emblem

問題へのリンク

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

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

    class CircleInfoDef
    {
        internal int X;
        internal int Y;
        internal double R;
    }
    static List<CircleInfoDef> mCircleInfoList1 = new List<CircleInfoDef>();
    static List<CircleInfoDef> mCircleInfoList2 = new List<CircleInfoDef>();

    static int mN;
    static int mM;

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

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

        SplitAct(InputList[0]);
        mN = wkArr[0];
        mM = wkArr[1];

        foreach (string EachStr in InputList.Skip(1).Take(mN)) {
            SplitAct(EachStr);
            var WillAdd = new CircleInfoDef();
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.R = wkArr[2];
            mCircleInfoList1.Add(WillAdd);
        }

        // 自由な半径を設定できる円が無い場合
        if (mM == 0) {
            Console.WriteLine(mCircleInfoList1.Min(pX => pX.R));
            return;
        }

        foreach (string EachStr in InputList.Skip(1 + mN)) {
            SplitAct(EachStr);
            var WillAdd = new CircleInfoDef();
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.R = 0;
            mCircleInfoList2.Add(WillAdd);
        }

        // 自由な半径を二分探索
        double L = 0;
        double R = 1;
        while (true) {
            if (CanAchieve(R) == false) {
                break;
            }
            R *= 2;
        }

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

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

    static bool CanAchieve(double pX)
    {
        for (int I = 0; I <= mCircleInfoList2.Count - 1; I++) {
            mCircleInfoList2[I].R = pX;
        }

        foreach (CircleInfoDef CircleInfo1 in mCircleInfoList1) {
            foreach (CircleInfoDef CircleInfo2 in mCircleInfoList2) {
                int Result = CheckTwoCircle(CircleInfo1, CircleInfo2);
                if (Result <= 3) return false;
            }
        }

        for (int I = 0; I <= mCircleInfoList2.Count - 1; I++) {
            for (int J = I + 1; J <= mCircleInfoList2.Count - 1; J++) {
                int Result = CheckTwoCircle(mCircleInfoList2[I], mCircleInfoList2[J]);
                if (Result <= 3) return false;
            }
        }
        return true;
    }

    // 円と円の位置関係を判定する
    // 判定1 一方の円が他方の円を完全に含み、2つの円は接していない
    // 判定2 一方の円が他方の円を完全に含み、2つの円は接している
    // 判定3 2つの円が互いに交差する
    // 判定4 2つの円の内部に共通部分は存在しないが、2つの円は接している
    // 判定5 2つの円の内部に共通部分は存在せず、2つの円は接していない
    static int CheckTwoCircle(CircleInfoDef pCircleInfo1, CircleInfoDef pCircleInfo2)
    {
        PointDef DiffVect = SetVector(pCircleInfo1.X, pCircleInfo1.Y,
                                      pCircleInfo2.X, pCircleInfo2.Y);
        long DiffVectNorm = DeriveNorm(DiffVect);

        double RDiff = pCircleInfo1.R - pCircleInfo2.R;
        double RDiffNorm = RDiff * RDiff;

        double RSum = pCircleInfo1.R + pCircleInfo2.R;
        double RSumNorm = RSum * RSum;

        // 判定1
        if (DiffVectNorm < RDiffNorm) {
            return 1;
        }

        // 判定2
        if (DiffVectNorm == RDiffNorm) {
            return 2;
        }

        // 判定3
        if (RDiffNorm < DiffVectNorm && DiffVectNorm < RSumNorm) {
            return 3;
        }

        // 判定4
        if (RSumNorm == DiffVectNorm) {
            return 4;
        }

        // 判定5
        return 5;
    }

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

    // ベクトルのNormを求める
    static int DeriveNorm(PointDef pVector)
    {
        return pVector.X * pVector.X + pVector.Y * pVector.Y;
    }
}

解説

半径の長さを二分探索してます。