ABC-075-D Axis-Parallel Rectangle

■■■問題■■■

2次元座標上にN個の点があります。
i(1 <= i <= N) 番目の点の座標は(xi,yi)です。

長方形の内部にN点のうちK個以上の点を含みつつ、それぞれの辺がX軸かY軸に平行な長方形を考えます。

このとき、長方形の辺上の点は長方形の内部に含みます。
それらの長方形の中で、最小の面積となるような長方形の面積を求めてください。

■■■入力■■■

N K
x1 y1
・
・
・
xN yN

●2 <= K <= N <= 50
●−10億 <= xi,yi <= 10億(1 <= i <= N)
●xi≠xj(1 <= i < j <= N)
●yi≠yj(1 <= i < j <= N)
●入力値はすべて整数である

■■■出力■■■

条件を満たす長方形の中で最小面積となるような長方形の面積を出力せよ

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 4");
            WillReturn.Add("1 4");
            WillReturn.Add("3 3");
            WillReturn.Add("6 2");
            WillReturn.Add("8 1");
            //21
            //条件を満たす最小面積となる長方形の1つは
            //(1,1),(8,1),(1,4),(8,4) の4つの頂点で構成されます。
            //その面積は (8-1)×(4-1)=21 であるため、21と出力します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 2");
            WillReturn.Add("0 0");
            WillReturn.Add("1 1");
            WillReturn.Add("2 2");
            WillReturn.Add("3 3");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 3");
            WillReturn.Add("-1000000000 -1000000000");
            WillReturn.Add("1000000000 1000000000");
            WillReturn.Add("-999999999 999999999");
            WillReturn.Add("999999999 -999999999");
            //3999999996000000001
            //オーバーフローに注意してください
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct XYInfo
    {
        internal int X;
        internal int Y;
    }

    struct KouhoInfo
    {
        internal int XFrom;
        internal int XTo;
        internal int YFrom;
        internal int YTo;
    }

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

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

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

        var XYList = new List<XYInfo>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYInfo WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            XYList.Add(WillAdd);
        }
        //X座標の昇順にソートしておく
        XYList.Sort((A, B) => A.X.CompareTo(B.X));
        int UB = XYList.Count - 1;

        var KouhoList = new List<KouhoInfo>();
        for (int LoopI = 0; LoopI <= UB; LoopI++) {
            for (int LoopJ = LoopI; LoopJ <= UB; LoopJ++) {
                for (int LoopK = 0; LoopK <= UB; LoopK++) {
                    for (int LoopL = 0; LoopL <= UB; LoopL++) {
                        if (XYList[LoopK].Y > XYList[LoopL].Y) continue;

                        KouhoInfo WillAdd;
                        WillAdd.XFrom = XYList[LoopI].X;
                        WillAdd.XTo = XYList[LoopJ].X;
                        WillAdd.YFrom = XYList[LoopK].Y;
                        WillAdd.YTo = XYList[LoopL].Y;
                        KouhoList.Add(WillAdd);
                    }
                }
            }
        }

        long AnswerMenseki = long.MaxValue;
        foreach (KouhoInfo EachKouho in KouhoList) {
            int NaihouCnt = 0;
            foreach (XYInfo EachXY in XYList) {
                if (EachKouho.XFrom <= EachXY.X && EachXY.X <= EachKouho.XTo
                 && EachKouho.YFrom <= EachXY.Y && EachXY.Y <= EachKouho.YTo) {
                    NaihouCnt++;
                }
            }
            if (NaihouCnt >= K) {
                long Width = Math.Abs(EachKouho.XTo - EachKouho.XFrom);
                long Height = Math.Abs(EachKouho.YTo - EachKouho.YFrom);

                long CurrMenseki = Width * Height;
                if (AnswerMenseki > CurrMenseki) {
                    AnswerMenseki = CurrMenseki;
                }
            }
        }
        Console.WriteLine(AnswerMenseki);
    }
}

解説

長方形の4隅は、必ず、いずれかの点ですので
4点の組み合わせを全探索してます。