← 返回题目列表

AtCoder · abc075_d

D. 轴平行矩形

中文机器翻译题面 查看原题

分数: 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

注意整数溢出。