トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

No.410 出会い

■■■問題■■■

最初A君はXY座標上の整数座標点Pにいて、B君は整数座標点Qにいます。

A君もB君も1秒あたりX軸方向に-1か+1もしくはY軸方向に-1か+1移動できます。
(移動は、X軸、Y軸の平行方向にしか移動できない)

A君とB君は最短時間で出会うための待ち合わせ場所を決めました。
A君とB君が同時にスタートして移動して出会うときの最短の時間を求めなさい。

■■■入力■■■

PX PY
QX QY

PX PY はA君の初期座標(PX,PY)。点Pは整数座標。
QX QY はB君の初期座標(QX,QY)。点Qは整数座標。
-10万 <= PX,PY,QX,QY <= 10万
点Pと点Qの座標は異なる。

■■■出力■■■

A君とB君が出会う最短の時間(秒)を1行で出力せよ。
数値自体があっているのであれば (20桁を目安) 冗長な小数点以下を出力してもよい。
最後に改行を忘れずに。


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("2 0");
            //1
            //A君は最初は点P(0,0)にいます。B君は最初は点Q(2,0)にいます。
            //点(1,0)を待ち合わせ場所にすれば1秒後に出会うことができます。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 0");
            WillReturn.Add("3 0");
            //1.5
            //A君は最初は点P(0,0)にいます。B君は最初は点Q(3,0)にいます。
            //(1.5,0)を待ち合わせ場所にすれば1.5秒後に出会うことができます。
            //待ち合わせ場所は必ずしも整数座標上でなくても良いです。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("0 0");
            WillReturn.Add("5 1");
            //3
            //A君は最初は点P(0,0)にいます。B君は最初は点Q(5,1)にいます。
            //例えば(3,0)を待ち合わせ場所にすれば3秒後に最短時間で出会えます。
            //待ち合わせ場所の候補は(3,0)以外にもあります。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("-12345 6789");
            WillReturn.Add("1234 -56789");
            //38578.5
            //入力の座標にはマイナス値も含まれるので注意してください
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        decimal[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => decimal.Parse(X)).ToArray();

        SplitAct(InputList[0]);
        decimal PX = wkArr[0], PY = wkArr[1];

        SplitAct(InputList[1]);
        decimal QX = wkArr[0], QY = wkArr[1];

        Console.WriteLine(Math.Abs(PX - QX) / 2M + Math.Abs(PY - QY) / 2M);
    }
}


解説

マンハッタン距離 / 2 が解となります。