P3681. 寻找矩形

题目描述

给定平面直角坐标系上的$N$个点，你需要找到一个面积最小的矩形，该矩形至少覆盖$M$个点。矩形的四个顶点坐标必须是整数，且边必须与坐标轴平行。如果一个点位于矩形的边上，则认为该点没有被覆盖。

输入格式

第一行输入测试用例的数量。
每个测试用例的第一行包含两个整数$N$和$M$（$1 \leq M \leq N \leq 200$）。
接下来的$N$行每行包含两个整数$x_i$, $y_i$（$1 \leq x_i, y_i \leq 10,000$），描述点的坐标。
每个测试用例之前有一个空行。

输出格式

对于每个测试用例，输出最小面积，每个结果占一行。

输入样例

5

2 1
200 6
100 5

2 2
200 6
100 5

2 1
1 1
1 1

2 2
1 1
1 1

8 5
5 7
6 6
6 8
7 5
7 9
8 6
8 8
9 7

输出样例

4
306
4
4
20

题目来源

POJ Founder Monthly Contest – 2008.07.27, windy7926778