CGL_7_D: Cross Points of a Circle and a Line

問題へのリンク

C#のソース

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

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

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

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

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

    struct SegmentDef
    {
        internal PointDef StaPos;
        internal PointDef EndPos;
    }

    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]);
        PointDef CirclePos;

        CirclePos.X = wkArr[0];
        CirclePos.Y = wkArr[1];
        decimal Circle_R = wkArr[2];

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            PointDef Line_Sta;
            Line_Sta.X = wkArr[0];
            Line_Sta.Y = wkArr[1];
            PointDef Line_End;
            Line_End.X = wkArr[2];
            Line_End.Y = wkArr[3];

            // 円の中心から直線の射影を求める
            SegmentDef InsSegment;
            InsSegment.StaPos = Line_Sta;
            InsSegment.EndPos = Line_End;

            PointDef ProjectPos = DeriveProjectPos(InsSegment, CirclePos);

            // 円の中心から直線の射影までの距離を求める
            PointDef VectorProject = SetVector(CirclePos, ProjectPos);
            decimal ProjectDistance = DeriveABS(VectorProject);

            // 三平方の定理で、射影からの線分の長さを求める
            decimal wkNorm = Circle_R * Circle_R - ProjectDistance * ProjectDistance;
            decimal BaseLen = (decimal)Math.Sqrt((double)wkNorm);

            // 直線の単位ベクトルを求める
            PointDef UnitVector = SetVector(Line_Sta, Line_End);
            decimal SavedABS = DeriveABS(UnitVector);
            UnitVector.X /= SavedABS;
            UnitVector.Y /= SavedABS;

            var AnswerPosList = new List<PointDef>();
            PointDef AnswerPos1 = ProjectPos;
            AnswerPos1.X += UnitVector.X * BaseLen;
            AnswerPos1.Y += UnitVector.Y * BaseLen;
            AnswerPosList.Add(AnswerPos1);
            PointDef AnswerPos2 = ProjectPos;
            AnswerPos2.X -= UnitVector.X * BaseLen;
            AnswerPos2.Y -= UnitVector.Y * BaseLen;
            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 DeriveDot(PointDef pVector1, PointDef pVector2)
    {
        return pVector1.X * pVector2.X + pVector1.Y * pVector2.Y;
    }

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

    // ベクトルの大きさを求める
    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;
    }

    // 点と直線の射影を求める
    static PointDef DeriveProjectPos(SegmentDef pSegment, PointDef pPoint)
    {
        // 処理01 内積からCosを求める
        PointDef Vector1 = SetVector(pSegment.StaPos, pPoint);
        PointDef Vector2 = SetVector(pSegment.StaPos, pSegment.EndPos);

        decimal CurrDot = DeriveDot(Vector1, Vector2);

        decimal Vector1_ABS = DeriveABS(Vector1);
        decimal Vector2_ABS = DeriveABS(Vector2);

        decimal CosVal;
        if (CurrDot == 0M) {
            CosVal = 0M;
        }
        else {
            CosVal = CurrDot / Vector1_ABS / Vector2_ABS;
        }

        // 処理02 P1 -> P2 と P1 -> X の比で、座標を求める
        decimal Distance_P1_X = Vector1_ABS * CosVal;

        decimal Project_X = pSegment.StaPos.X + Vector2.X * Distance_P1_X / Vector2_ABS;
        decimal Project_Y = pSegment.StaPos.Y + Vector2.Y * Distance_P1_X / Vector2_ABS;

        PointDef WillReturn;
        WillReturn.X = Project_X;
        WillReturn.Y = Project_Y;
        return WillReturn;
    }
}

解説

射影の座標を求めてから、三平方の定理を使ってます。