ABC467-D Concentric Circles

問題へのリンク

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

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

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

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long PX = wkArr[0];
            long PY = wkArr[1];
            long QX = wkArr[2];
            long QY = wkArr[3];
            long RX = wkArr[4];
            long RY = wkArr[5];
            long SX = wkArr[6];
            long SY = wkArr[7];
            bool Result = Solve(PX, PY, QX, QY, RX, RY, SX, SY);
            Console.WriteLine(Result ? "Yes" : "No");
        }
    }

    static bool Solve(long pPX, long pPY, long pQX, long pQY,
                      long pRX, long pRY, long pSX, long pSY)
    {
        long A1, B1, C1;
        long A2, B2, C2;

        DeriveTyokusenABC(pPX, pPY, pQX, pQY, out A1, out B1, out C1);
        DeriveTyokusenABC(pRX, pRY, pSX, pSY, out A2, out B2, out C2);

        // 法線ベクトル同士の外積を求める
        PointDef Vect1 = new PointDef() { X = A1, Y = B1 };
        PointDef Vect2 = new PointDef() { X = A2, Y = B2 };

        long Cross1 = DeriveCross(Vect1, Vect2);
        if (Cross1 != 0) {
            return true;
        }

        // 中点から中点までのベクトル
        long X1 = pPX + pQX;
        long Y1 = pPY + pQY;

        long X2 = pRX + pSX;
        long Y2 = pRY + pSY;

        PointDef Vect3 = new PointDef() { X = X1 - X2, Y = Y1 - Y2 };

        long Cross2 = DeriveCross(Vect1, Vect3);
        if (Cross2 == 0) {
            return true;
        }
        return false;
    }

    // (X1,Y1) , (X2,Y2) を引数とし、2点を通る直線の、aX + bY + c = 0 の (a,b,c)を設定
    static void DeriveTyokusenABC(long pX1, long pY1, long pX2, long pY2,
        out long pA, out long pB, out long pC)
    {
        long S = pX2 - pX1;
        long T = pY2 - pY1;
        pA = -T;
        pB = S;
        pC = T * pX1 - S * pY1;
    }

    // 外積を求める
    static long DeriveCross(PointDef pVector1, PointDef pVector2)
    {
        return pVector1.X * pVector2.Y - pVector1.Y * pVector2.X;
    }
}

解説

円の2点間の法線ベクトルは、
円の2点間の直線の式が aX + bY + c = 0 であれば、
(a,b) となります。

法線ベクトル同士が平行でなければ、交点を持ちますが
法線ベクトル同士の平行判定は、外積が0かで判定可能です。

法線ベクトルが平行な場合、
垂直二等分線が中点2つを通るかは、
中点か中点までのベクトルと、垂直二等分線
との平行判定で判定できます。