ABC075 D - Axis-Parallel Rectangle

問題
提出コード

解法

まずは、4点を決めます。同じ頂点を選んでも問題ないです。
そうしたら、その4点を含むような長方形のうち最小のものを求めます。
この長方形の座標は、
右、上:それぞれ4点のx座標、y座標のうち最大のもの
左、下:それぞれ4点のx座標、y座標のうち最小のもの
となります。
ここまできたら、あとは、この長方形の中に含まれている点の個数を数えます。
これは、すべての点に対して、先ほどの上下左右の範囲内に収まっているかどうかを調べることで判別できます。
含まれている点の個数がk個以上だった場合、長方形の面積の最小値を更新します。
(上 - 下)×(右 - 左)
によって求めることができるので、この最小値が答えになります。
あとは、最初に決める4点を全探索すれば、で求めることができます。