问题1037--寻找最小矩形

1037: 寻找最小矩形

时间限制: 2 Sec  内存限制: 128 MB
提交: 41  解决: 18
[提交] [状态] [讨论版] [命题人:]

题目描述

给定N个点和一个数值M,然后给你N个坐标(xi, yi), 这些坐标都是整数点(1 <= xi, yi <=10000),现在罗老师想知道,如果我要用一个矩形去覆盖这些坐标,至少覆盖M个点,这个矩形面积至少多大。为了方便,矩形的四个点的坐标必须是整数,长和宽都要平行于x轴和y轴,点在矩形的边上不算覆盖。

求,矩形的最小面积

输入

输入N,M (1 <= M <= N <= 500)

然后N行,每行输入(xi, yi)

输出

输出最小面积

样例输入 Copy

2 1
200 6
100 5

样例输出 Copy

4

提示

【样例说明】

如果覆盖(100,5)这个点,矩形左下,右上坐标可以是(99,4)(101,6),面积为4

其他样例:

输入:

2 2

200 6

100 5

输出:

306

 

输入:

8 5

5 7

6 6

6 8

7 5

7 9

8 6

8 8

9 7

输出:

20

来源/分类

枚举