分数: 400 点
问题陈述
我们有 N 点位于二维平面中。
的坐标 i第一点 (1 \leq i \leq N) 是 (x_i,y_i).
让我们考虑一个矩形,其边平行于坐标轴,其中包含 K 或更多 N 指向其内部。
这里,矩形边上的点被认为位于内部。
找到这样一个矩形的最小可能面积。
约束
- 2 \leq K \leq N \leq 50
- -10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N)
- x_i≠x_j (1 \leq i<j \leq N)
- y_i≠y_j (1 \leq i<j \leq N)
- 所有输入值均为整数。 (日本标准时间 21:50 添加)
输入
输入由标准输入按以下格式给出:
N K
x_1 y_1
:
x_{N} y_{N}
输出
打印满足条件的矩形的最小可能面积。
示例输入 1
4 4 1 4 3 3 6 2 8 1
示例输出 1
21
满足最小可能面积条件的一个矩形具有以下顶点: (1,1), (8,1), (1,4) 和 (8,4).
它的面积是 (8-1) × (4-1) = 21.
示例输入 2
4 2 0 0 1 1 2 2 3 3
示例输出 2
1
示例输入 3
4 3 -1000000000 -1000000000 1000000000 1000000000 -999999999 999999999 999999999 -999999999
示例输出 3
3999999996000000001
注意整数溢出。