ABC426-E Closest Moment

問題へのリンク

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("4");
            WillReturn.Add("0 0 -2 2");
            WillReturn.Add("-1 -1 4 4");
            WillReturn.Add("4 0 2 0");
            WillReturn.Add("6 0 8 0");
            WillReturn.Add("1 0 1 1");
            WillReturn.Add("-1 0 1 1");
            WillReturn.Add("-8 9 2 6");
            WillReturn.Add("-10 -10 17 20");
            //1.000000000000000
            //2.000000000000000
            //0.000000000000000
            //1.783905950993199
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static double[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => double.Parse(pX)).ToArray();
    }

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

        double[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        var sb = new System.Text.StringBuilder();
        for (int I = 1; I <= InputList.Count - 1; I += 2) {
            SplitAct(InputList[I]);
            mTakaStaX = wkArr[0];
            mTakaStaY = wkArr[1];
            mTakaEndX = wkArr[2];
            mTakaEndY = wkArr[3];

            SplitAct(InputList[I + 1]);
            mAokiStaX = wkArr[0];
            mAokiStaY = wkArr[1];
            mAokiEndX = wkArr[2];
            mAokiEndY = wkArr[3];

            double Answer = Solve();
            sb.Append(Answer);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    static double mTakaStaX, mTakaStaY;
    static double mTakaEndX, mTakaEndY;

    static double mAokiStaX, mAokiStaY;
    static double mAokiEndX, mAokiEndY;

    static double mTakaVectX, mTakaVectY;
    static double mAokiVectX, mAokiVectY;

    static double mKyoriTaka;
    static double mKyoriAoki;

    static double Solve()
    {
        mKyoriTaka = DeriveKyori(mTakaStaX, mTakaStaY, mTakaEndX, mTakaEndY);
        mKyoriAoki = DeriveKyori(mAokiStaX, mAokiStaY, mAokiEndX, mAokiEndY);

        mTakaVectX = (mTakaEndX - mTakaStaX) / mKyoriTaka;
        mTakaVectY = (mTakaEndY - mTakaStaY) / mKyoriTaka;

        mAokiVectX = (mAokiEndX - mAokiStaX) / mKyoriAoki;
        mAokiVectY = (mAokiEndY - mAokiStaY) / mKyoriAoki;

        double Range1Sta = 0;
        double Range1End = Math.Min(mKyoriTaka, mKyoriAoki);
        double Answer = double.MaxValue;
        Answer = Math.Min(Answer, ExecSanbuntansaku(Range1Sta, Range1End));

        double Range2Sta = Range1End;
        double Range2End = Math.Max(mKyoriTaka, mKyoriAoki);
        Answer = Math.Min(Answer, ExecSanbuntansaku(Range2Sta, Range2End));

        return Answer;
    }

    // ユークリッド距離を求める
    static double DeriveKyori(double pStaX, double pStaY, double pEndX, double pEndY)
    {
        double DiffX = pStaX - pEndX;
        double DiffY = pStaY - pEndY;

        return Math.Sqrt(DiffX * DiffX + DiffY * DiffY);
    }

    // 三分探索で極小値を求める
    static double ExecSanbuntansaku(double pRangeSta, double pRangeEnd)
    {
        double L = pRangeSta;
        double R = pRangeEnd;

        // ★★★ ここのwhile条件は、問題の要求精度によって変更を検討 ★★★
        //while (L + 0.0000001D < R) {
        while (L + double.Epsilon < R) {
            double BeforeL = L, BeforeR = R;

            double C1 = (L * 2 + R) / 3;
            double C2 = (L + R * 2) / 3;

            double C1Val = DeriveFrucResult(C1);
            double C2Val = DeriveFrucResult(C2);

            if (C1Val < C2Val) {
                R = C2;
            }
            else {
                L = C1;
            }

            // 変化がなかったら、Break
            if (L == BeforeL && R == BeforeR) {
                break;
            }
        }

        var MinKouhoList = new List<double>();
        MinKouhoList.Add(DeriveFrucResult(L));
        MinKouhoList.Add(DeriveFrucResult(R));
        return MinKouhoList.Min();
    }

    // 経過時間を引数として、距離を返す
    static double DeriveFrucResult(double pElapsed)
    {
        double TakaX = mTakaStaX + mTakaVectX * Math.Min(pElapsed, mKyoriTaka);
        double TakaY = mTakaStaY + mTakaVectY * Math.Min(pElapsed, mKyoriTaka);

        double AokiX = mAokiStaX + mAokiVectX * Math.Min(pElapsed, mKyoriAoki);
        double AokiY = mAokiStaY + mAokiVectY * Math.Min(pElapsed, mKyoriAoki);

        return DeriveKyori(TakaX, TakaY, AokiX, AokiY);
    }
}

解説

両方とも移動してる場合の極小値を三分探索で求め、
片方だけ移動してる場合の極小値も三分探索で求めてます。