CGL_7_E: Cross Points of Circles

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q066 円の交点 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_E&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("0 0 2");
            WillReturn.Add("2 0 2");
            //1.00000000 -1.73205080 1.00000000 1.73205080
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 0 2");
            WillReturn.Add("0 3 1");
            //0.00000000 2.00000000 0.00000000 2.00000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

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

        SplitAct(InputList[0]);
        decimal C1X = wkArr[0];
        decimal C1Y = wkArr[1];
        decimal C1R = wkArr[2];

        SplitAct(InputList[1]);
        decimal C2X = wkArr[0];
        decimal C2Y = wkArr[1];
        decimal C2R = wkArr[2];

        // 処理01 C1 -> C2 のベクトルを求める
        PointDef C1_Pos = new PointDef() { X = C1X, Y = C1Y };
        PointDef C2_Pos = new PointDef() { X = C2X, Y = C2Y };

        PointDef Vector1_D = SetVector(C1_Pos, C2_Pos);
        decimal Vector1_D_ABS = DeriveABS(Vector1_D);

        // 処理02 余弦定理でC1のCosを求める
        decimal Cos = (C2R * C2R - C1R * C1R - Vector1_D_ABS * Vector1_D_ABS) /
            (-2 * C1R * Vector1_D_ABS);

        // 処理03 SinとCosの公式でSinを求める
        decimal Sin = DeriveDecimalSqrt(1 - Cos * Cos);

        // 処理04 C1 -> C2 の単位ベクトルの、C1R倍のベクトルを求める
        PointDef Vector_Unit = Vector1_D;
        Vector_Unit.X /= Vector1_D_ABS;
        Vector_Unit.Y /= Vector1_D_ABS;
        PointDef Vector_KD = Vector_Unit;
        Vector_KD.X *= C1R;
        Vector_KD.Y *= C1R;

        // 処理05 一次変換を使って、KDをQ度回転させたベクトルを求める
        PointDef Kiten_Vector1 = Exec1JiHenkan(Vector_KD, Sin, Cos);

        // 処理06 一次変換を使って、KDをマイナスQ度回転させたベクトルを求める
        PointDef Kiten_Vector2 = Exec1JiHenkan(Vector_KD, -Sin, Cos);

        // 処理07 解を出力
        var AnswerPosList = new List<PointDef>();
        PointDef AnswerPos1 = C1_Pos;
        AnswerPos1.X += Kiten_Vector1.X;
        AnswerPos1.Y += Kiten_Vector1.Y;
        AnswerPosList.Add(AnswerPos1);
        PointDef AnswerPos2 = C1_Pos;
        AnswerPos2.X += Kiten_Vector2.X;
        AnswerPos2.Y += Kiten_Vector2.Y;
        AnswerPosList.Add(AnswerPos2);

        AnswerPosList = AnswerPosList.OrderBy(pX => pX.X).ThenBy(pX => pX.Y).ToList();
        Console.WriteLine("{0} {1} {2} {3}",
            AnswerPosList[0].X, AnswerPosList[0].Y,
            AnswerPosList[1].X, AnswerPosList[1].Y);
    }

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

    // ベクトルの大きさを求める
    static decimal DeriveABS(PointDef pVector)
    {
        decimal wkNorm = DeriveNorm(pVector);
        double wkSqrt = Math.Sqrt((double)wkNorm);
        return (decimal)wkSqrt;
    }

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

    // Decimal型のSqrtを返す
    static decimal DeriveDecimalSqrt(decimal pDec)
    {
        return (decimal)(Math.Sqrt((double)pDec));
    }

    // ベクトルとSinとCosを引数として、回転したベクトルを返す
    static PointDef Exec1JiHenkan(PointDef pPos, decimal pSin, decimal pCos)
    {
        PointDef WillReturn;
        WillReturn.X = pCos * pPos.X + pPos.Y * -pSin;
        WillReturn.Y = pSin * pPos.X + pPos.Y * pCos;
        return WillReturn;
    }
}

解説

余弦定理や一次変換を使ってます。