AOJ 0563 歩くサンタクロース

問題へのリンク(AOJ)
問題へのリンク(AtCoder)

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("5 4");
            WillReturn.Add("3");
            WillReturn.Add("1 1");
            WillReturn.Add("3 4");
            WillReturn.Add("5 3");
            //10
            //3 3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 6");
            WillReturn.Add("8");
            WillReturn.Add("1 3");
            WillReturn.Add("3 2");
            WillReturn.Add("4 4");
            WillReturn.Add("2 5");
            WillReturn.Add("2 3");
            WillReturn.Add("3 3");
            WillReturn.Add("3 4");
            WillReturn.Add("2 4");
            //21
            //2 3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

    struct PointDef
    {
        internal long X;
        internal long Y;
    }
    static List<PointDef> mPointList = new List<PointDef>();
    static long UB;

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

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

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            mPointList.Add(WillAdd);
        }

        UB = mPointList.Count - 1;

        // X座標の中央値付近の値Listを求める
        var XArr = mPointList.Select(pX => pX.X).ToArray();
        Array.Sort(XArr);
        var NearMedianXList = DeriveNearMedianList(XArr);

        // Y座標の中央値を求める
        var YArr = mPointList.Select(pX => pX.Y).ToArray();
        Array.Sort(YArr);
        var NearMedianYList = DeriveNearMedianList(YArr);

        long AnswerVal = long.MaxValue;
        long AnswerX = -1;
        long AnswerY = -1;
        foreach (long EachX in NearMedianXList) {
            foreach (long EachY in NearMedianYList) {
                System.GC.Collect();
                long AnswerKouho = DeriveAnswerKouho(EachX, EachY);
                if (AnswerKouho < AnswerVal) {
                    AnswerVal = AnswerKouho;
                    AnswerX = EachX;
                    AnswerY = EachY;
                }
            }
        }
        Console.WriteLine(AnswerVal);
        Console.WriteLine("{0} {1}", AnswerX, AnswerY);
    }

    // 基点とする座標を引数として解候補を返す
    static long DeriveAnswerKouho(long pBaseX, long pBaseY)
    {
        PointDef[] SortedArr =
            mPointList.OrderBy(pX => Math.Abs(pBaseX - pX.X) + Math.Abs(pBaseY - pX.Y)).ToArray();

        long Answer = 0;
        for (long I = 0; I <= UB; I++) {
            long Diff = Math.Abs(pBaseX - SortedArr[I].X) + Math.Abs(pBaseY - SortedArr[I].Y);
            if (I < UB) {
                Answer += Diff * 2;
            }
            else {
                Answer += Diff;
            }
        }
        return Answer;
    }

    // 配列を引数として、中央値付近の値Listを返す
    static List<long> DeriveNearMedianList(long[] pArr)
    {
        var NearMedianList = new List<long>();

        Predicate<long> IsValidInd = (pInd) =>
        {
            return 0 <= pInd && pInd <= UB;
        };

        long MidInd = UB / 2;
        if (IsValidInd(MidInd - 1)) NearMedianList.Add(pArr[MidInd - 1]);
        if (IsValidInd(MidInd)) NearMedianList.Add(pArr[MidInd]);
        if (IsValidInd(MidInd + 1)) NearMedianList.Add(pArr[MidInd + 1]);

        return NearMedianList;
    }
}

解説

まずは、縦と横を独立に考え、横だけで考えます。
A B         C D
基準点は、BからCの間になります。
Bより左ならば、右に基準点を動かすほど得であり、
Cより右ならば、左に基準点を動かすほど得だからです。

後は、片道で済む移動を考えて、
BからCの間のどこを基準点にするのが最適かを考える必要がありますが
これは、結局は、最も遠い点までの距離を最小化できれば最適なので、
BとCの両方を候補にし、縦方向も同様とし、
全組み合わせを最もコストの安い基準点を採用すれば良いです。