A42 Soccer

問題へのリンク

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 30");
            WillReturn.Add("20 30");
            WillReturn.Add("10 40");
            WillReturn.Add("50 10");
            WillReturn.Add("30 60");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        SplitAct(InputList[0]);
        int K = wkArr[1];

        int CurrPointNo = 0;
        var PointInfoList = new List<PointInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PointInfoDef WillAdd;
            WillAdd.PointNo = CurrPointNo++;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            PointInfoList.Add(WillAdd);
        }
        var InsKdTree = new KdTree(PointInfoList.ToArray());

        int[] XArr = PointInfoList.Select(pX => pX.X).Distinct().ToArray();
        int[] YArr = PointInfoList.Select(pX => pX.Y).Distinct().ToArray();

        long Answer = long.MinValue;
        foreach (int EachX in XArr) {
            foreach (int EachY in YArr) {
                InsKdTree.mPointCnt = 0;
                InsKdTree.Find(0, EachX, EachX + K, EachY, EachY + K, 0);
                Answer = Math.Max(Answer, InsKdTree.mPointCnt);
            }
        }
        Console.WriteLine(Answer);
    }
}

internal struct PointInfoDef
{
    internal int PointNo;
    internal int X;
    internal int Y;
}

// KdTreeクラス
internal class KdTree
{
    const int NIL = -1;
    private int mCurrNode;
    private PointInfoDef[] mArr;

    // コンストラクタ
    internal KdTree(PointInfoDef[] pArr)
    {
        mCurrNode = 0;
        mArr = pArr;
        Make2DTree(0, mArr.GetUpperBound(0), 0);
    }

    private struct NodeInfoDef
    {
        internal int ArrInd;
        internal int LeftNode;
        internal int RightNode;
    }
    private Dictionary<int, NodeInfoDef> mNodeInfoDict = new Dictionary<int, NodeInfoDef>();

    private class SortX : System.Collections.Generic.IComparer<PointInfoDef>
    {
        public int Compare(PointInfoDef a, PointInfoDef b)
        {
            return a.X.CompareTo(b.X);
        }
    }

    private class SortY : System.Collections.Generic.IComparer<PointInfoDef>
    {
        public int Compare(PointInfoDef a, PointInfoDef b)
        {
            return a.Y.CompareTo(b.Y);
        }
    }

    private int Make2DTree(int pLeftNode, int pRightNode, int pDepth)
    {
        // 部分ソート (pLeftNodeからpRightNodeまで)
        if (pDepth % 2 == 0) {
            Array.Sort(mArr, pLeftNode, pRightNode - pLeftNode + 1, new SortX());
        }
        else {
            Array.Sort(mArr, pLeftNode, pRightNode - pLeftNode + 1, new SortY());
        }

        int Mid = (pLeftNode + pRightNode) / 2;

        int Node = mCurrNode++;
        NodeInfoDef WillAdd;
        WillAdd.ArrInd = Mid;

        // 左部分木の設定
        WillAdd.LeftNode = NIL;
        if (pLeftNode <= Mid - 1) {
            WillAdd.LeftNode = Make2DTree(pLeftNode, Mid - 1, pDepth + 1);
        }

        // 右部分木の設定
        WillAdd.RightNode = NIL;
        if (Mid + 1 <= pRightNode) {
            WillAdd.RightNode = Make2DTree(Mid + 1, pRightNode, pDepth + 1);
        }

        mNodeInfoDict[Node] = WillAdd;

        return Node;
    }

    internal int mPointCnt = 0;

    internal void Find(int pCurrNode, int pXFrom, int pXTo, int pYFrom, int pYTo, int pDepth)
    {
        NodeInfoDef CurrNodeInfo = mNodeInfoDict[pCurrNode];
        int CurrX = mArr[CurrNodeInfo.ArrInd].X;
        int CurrY = mArr[CurrNodeInfo.ArrInd].Y;

        if (pXFrom <= CurrX && CurrX <= pXTo
         && pYFrom <= CurrY && CurrY <= pYTo) {
            mPointCnt++;
        }

        if (pDepth % 2 == 0) {
            // 左部分木を探索
            if (CurrNodeInfo.LeftNode != NIL && pXFrom <= CurrX) {
                Find(CurrNodeInfo.LeftNode, pXFrom, pXTo, pYFrom, pYTo, pDepth + 1);
            }

            // 右部分木を探索
            if (CurrNodeInfo.RightNode != NIL && CurrX <= pXTo) {
                Find(CurrNodeInfo.RightNode, pXFrom, pXTo, pYFrom, pYTo, pDepth + 1);
            }
        }
        else {
            // 左部分木を探索
            if (CurrNodeInfo.LeftNode != NIL && pYFrom <= CurrY) {
                Find(CurrNodeInfo.LeftNode, pXFrom, pXTo, pYFrom, pYTo, pDepth + 1);
            }

            // 右部分木を探索
            if (CurrNodeInfo.RightNode != NIL && CurrY <= pYTo) {
                Find(CurrNodeInfo.RightNode, pXFrom, pXTo, pYFrom, pYTo, pDepth + 1);
            }
        }
    }

    internal void DebugPrint()
    {
        foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
            Console.WriteLine("mTreeInfoDict[{0}] ArrInd={1} LeftNode={2} RightNode={3}",
                EachPair.Key,
                EachPair.Value.ArrInd,
                EachPair.Value.LeftNode,
                EachPair.Value.RightNode);
        }
    }
}

解説

KdTreeで解いてます。