ARC042-B アリの高橋くん

問題へのリンク

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("0 0");
            WillReturn.Add("4");
            WillReturn.Add("100 100");
            WillReturn.Add("-100 100");
            WillReturn.Add("-100 -100");
            WillReturn.Add("100 -100");
            //100
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 10");
            WillReturn.Add("3");
            WillReturn.Add("0 100");
            WillReturn.Add("-100 -100");
            WillReturn.Add("100 -100");
            //31.3049516850
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("34 6");
            WillReturn.Add("7");
            WillReturn.Add("-43 -65");
            WillReturn.Add("-23 -99");
            WillReturn.Add("54 -68");
            WillReturn.Add("65 92");
            WillReturn.Add("16 83");
            WillReturn.Add("-18 43");
            WillReturn.Add("-39 2");
            //25.0284205314
        }
        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 StaPos;
        StaPos.X = wkArr[0];
        StaPos.Y = wkArr[1];

        var PointList = new List<PointDef>();
        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            PointList.Add(WillAdd);
        }

        var SegmentList = new List<SegmentDef>();
        for (int I = 1; I <= PointList.Count - 1; I++) {
            SegmentDef WillAdd1;
            WillAdd1.StaPos = PointList[I - 1];
            WillAdd1.EndPos = PointList[I];
            SegmentList.Add(WillAdd1);
        }
        SegmentDef WillAdd2;
        WillAdd2.StaPos = PointList.Last();
        WillAdd2.EndPos = PointList[0];
        SegmentList.Add(WillAdd2);

        var AnswerKouho = new List<decimal>();
        foreach (SegmentDef EachSegment in SegmentList) {
            decimal Kouho = GetDistanceSP(EachSegment, StaPos);
            AnswerKouho.Add(Kouho);
        }
        Console.WriteLine(AnswerKouho.Min());
    }

    // 点と線分の距離を求める
    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;
    }
}

解説

点と線分との距離を求めて
その最小値が解になります。

類題

AOJ CGL_2_D: Distance