CGL_2_D: Distance

問題へのリンク

C#のソース

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

// Q061 距離 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_D&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 1 0 0 1 1 1");
            WillReturn.Add("0 0 1 0 2 1 1 2");
            WillReturn.Add("-1 0 1 0 0 1 0 -1");
            //1.0000000000
            //1.4142135624
            //0.0000000000
        }
        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();

        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];

            SegmentDef Segment1;
            Segment1.StaPos = Point1; Segment1.EndPos = Point2;
            SegmentDef Segment2;
            Segment2.StaPos = Point3; Segment2.EndPos = Point4;

            Console.WriteLine(GetDistance(Segment1, Segment2));
        }
    }

    // 線分と線分の距離を求める
    static decimal GetDistance(SegmentDef pSegment1, SegmentDef pSegment2)
    {
        // 線分同士が交差する場合
        if (IsIntersect(pSegment1, pSegment2)) {
            return 0M;
        }

        var KouhoList = new List<decimal>();
        KouhoList.Add(GetDistanceSP(pSegment1, pSegment2.StaPos));
        KouhoList.Add(GetDistanceSP(pSegment1, pSegment2.EndPos));
        KouhoList.Add(GetDistanceSP(pSegment2, pSegment1.StaPos));
        KouhoList.Add(GetDistanceSP(pSegment2, pSegment1.EndPos));
        return KouhoList.Min();
    }

    // 線分同士の交差判定
    static bool IsIntersect(SegmentDef pSegment1, SegmentDef pSegment2)
    {
        PointDef P1 = pSegment1.StaPos;
        PointDef P2 = pSegment1.EndPos;
        PointDef P3 = pSegment2.StaPos;
        PointDef P4 = pSegment2.EndPos;

        if (CCW(P1, P2, P3) * CCW(P1, P2, P4) <= 0 &&
            CCW(P3, P4, P1) * CCW(P3, P4, P2) <= 0) {
            return true;
        }
        return false;
    }

    static int CCW(PointDef pPointA, PointDef pPointB, PointDef pPointC)
    {
        const int COUNTER_CLOCKWISE = 1;
        const int CLOCKWISE = -1;
        const int ONLINE_BACK = 2;
        const int ONLINE_FRONT = -2;
        const int ON_SEGMENT = 0;

        PointDef VectorA = SetVector(pPointA, pPointB);
        PointDef VectorB = SetVector(pPointA, pPointC);

        // 外積 A*Bを求める
        decimal Cross = DeriveCross(VectorA, VectorB);

        // Aの半時計回りの方向にBが存在する
        if (Cross > 0) {
            return COUNTER_CLOCKWISE;
        }

        // Aの時計回りの方向にBが存在する
        if (Cross < 0) {
            return CLOCKWISE;
        }

        // 3点が1直線にある場合

        // 内積がマイナスなら、ベクトルの向きは反対
        decimal Dot = DeriveDot(VectorA, VectorB);
        if (Dot < 0) {
            return ONLINE_BACK;
        }

        decimal NormA = DeriveNorm(VectorA);
        decimal NormB = DeriveNorm(VectorB);
        if (NormA < NormB) {
            return ONLINE_FRONT;
        }
        return ON_SEGMENT;
    }

    // 点と線分の距離を求める
    static decimal GetDistanceSP(SegmentDef pSegment, PointDef pPoint)
    {
        // 判定1 p1を始点とし、pまでのベクトルとp2までのベクトルの内積で判定
        PointDef Vector_p1_p = SetVector(pSegment.StaPos, pPoint);
        PointDef Vector_p1_p2 = SetVector(pSegment.StaPos, pSegment.EndPos);
        if (DeriveDot(Vector_p1_p, Vector_p1_p2) < 0M) {
            return DeriveABS(Vector_p1_p);
        }

        // 判定2 p2を始点とし、pまでのベクトルとp1までのベクトルの内積で判定
        PointDef Vector_p2_p = SetVector(pSegment.EndPos, pPoint);
        PointDef Vector_p2_p1 = SetVector(pSegment.EndPos, pSegment.StaPos);
        if (DeriveDot(Vector_p2_p, Vector_p2_p1) < 0M) {
            return DeriveABS(Vector_p2_p);
        }

        return GetDistanceLP(pSegment, pPoint);
    }

    // 始点と終点の座標を引数として、始点から終点へのベクトルを返す
    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 decimal GetDistanceLP(SegmentDef pSegment, PointDef pPoint)
    {
        PointDef Vector_p1_p2 = SetVector(pSegment.StaPos, pSegment.EndPos);
        PointDef Vector_p1_p = SetVector(pSegment.StaPos, pPoint);

        // 平行四辺形の面積 (外積の絶対値) を求める
        decimal wkCross = DeriveCross(Vector_p1_p2, Vector_p1_p);
        decimal wkABS = DeriveABS(Vector_p1_p2);

        return Math.Abs(wkCross) / wkABS;
    }
}

解説

2つの線分が交点を持つ場合は、距離は0
2つの線分が交点を持たない場合は、4つの候補の中の最小の距離となります。