ABC259-D Circumferences

問題へのリンク

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

    static long mSX;
    static long mSY;
    static long mTX;
    static long mTY;

    struct CircleInfoDef
    {
        internal long X;
        internal long Y;
        internal long R;
    }

    static List<CircleInfoDef> mCircleInfoList = new List<CircleInfoDef>();

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

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

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

        SplitAct(InputList[1]);
        mSX = wkArr[0];
        mSY = wkArr[1];
        mTX = wkArr[2];
        mTY = wkArr[3];

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

        if (ExecBFS()) {
            Console.WriteLine("Yes");
        }
        else {
            Console.WriteLine("No");
        }
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
    }

    static bool ExecBFS()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        for (int I = 0; I <= mCircleInfoList.Count - 1; I++) {
            if (HasPoint(mSX, mSY, mCircleInfoList[I])) {
                WillPush.CurrInd = I;
                Stk.Push(WillPush);
            }
        }

        var VisitedSet = new HashSet<int>();

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (HasPoint(mTX, mTY, mCircleInfoList[Popped.CurrInd])) {
                return true;
            }

            for (int I = 0; I <= mCircleInfoList.Count - 1; I++) {
                if (VisitedSet.Contains(I)) continue;

                if (HasCross(mCircleInfoList[Popped.CurrInd], mCircleInfoList[I])) {
                    VisitedSet.Add(I);
                    WillPush.CurrInd = I;
                    Stk.Push(WillPush);
                }
            }
        }
        return false;
    }

    // 円の軌跡が指定座標を含むかを返す
    static bool HasPoint(long pX, long pY, CircleInfoDef pCircleInfo)
    {
        long DiffX = pCircleInfo.X - pX;
        long DiffY = pCircleInfo.Y - pY;
        long R = pCircleInfo.R;

        return R * R == (DiffX * DiffX) + (DiffY * DiffY);
    }

    // 円と円が交点を持つかを返す
    static bool HasCross(CircleInfoDef pCircleInfo1, CircleInfoDef pCircleInfo2)
    {
        PointDef DiffVect = SetVector(pCircleInfo1.X, pCircleInfo1.Y,
                                      pCircleInfo2.X, pCircleInfo2.Y);
        long DiffVectNorm = DeriveNorm(DiffVect);

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

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

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

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

        // 判定04
        if (RSumNorm == DiffVectNorm) {
            return true;
        }
        return false;
    }

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

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

解説

遷移可能かを判定しながらDFSを行ってます。

類題

E8本(数学) 035 Two Circles