CGL_2_C: Cross Point

問題へのリンク

C#のソース

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

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

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("0 0 2 0 1 1 1 -1");
            WillReturn.Add("0 0 1 1 0 1 1 0");
            WillReturn.Add("0 0 1 1 1 0 0 1");
            //1.0000000000 0.0000000000
            //0.5000000000 0.5000000000
            //0.5000000000 0.5000000000
        }
        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();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PointDef Point1, Point2, Point3, Point4;
            Point1.X = wkArr[0]; Point1.Y = wkArr[1];
            Point2.X = wkArr[2]; Point2.Y = wkArr[3];
            Point3.X = wkArr[4]; Point3.Y = wkArr[5];
            Point4.X = wkArr[6]; Point4.Y = wkArr[7];

            PointDef Vector12 = SetVector(Point1, Point2);
            PointDef Vector34 = SetVector(Point3, Point4);

            PointDef Vector13 = SetVector(Point1, Point3);
            PointDef Vector24 = SetVector(Point2, Point4);

            // P1P2とP1P3からなる平行四辺形の面積
            decimal AbsCross1 = Math.Abs(DeriveCross(Vector12, Vector13));

            // P2P1とP2P4からなる平行四辺形の面積
            decimal AbsCross2 = Math.Abs(DeriveCross(Vector12, Vector24));

            // P3からP1P2への垂線の長さ
            decimal Height1 = AbsCross1 / DeriveABS(Vector12);

            // P4からP1P2への垂線の長さ
            decimal Height2 = AbsCross2 / DeriveABS(Vector12);

            // 内分点の公式で、P3とP4をHeight1:Height2に内分する点を求める
            decimal AnswerX = (Height2 * Point3.X + Height1 * Point4.X) / (Height2 + Height1);
            decimal AnswerY = (Height2 * Point3.Y + Height1 * Point4.Y) / (Height2 + Height1);
            Console.WriteLine("{0} {1}", AnswerX, AnswerY);
        }
    }

    // 始点と終点の座標を引数として、始点から終点へのベクトルを返す
    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 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;
    }
}

解説

外積から垂線の長さを求め、
内分点の公式を使ってます。