D - Axis-Parallel Rectangle

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

2次元座標上に N 個の点があります。
i(1≦i≦N) 番目の点の座標は (x_i,y_i) です。
長方形の内部に N 点のうち K 個以上の点を含みつつ、それぞれの辺がX軸かY軸に平行な長方形を考えます。
このとき、長方形の辺上の点は長方形の内部に含みます。
それらの長方形の中で、最小の面積となるような長方形の面積を求めてください。

制約

  • 2≦K≦N≦50
  • -10^9≦x_i,y_i≦10^9 (1≦i≦N)
  • x_i≠x_j (1≦i<j≦N)
  • y_i≠y_j (1≦i<j≦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,1),(8,1),(1,4),(8,4)4 つの頂点で構成されます。
その面積は (8-1) × (4-1) = 21 であるため、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

オーバーフローに注意してください。

Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.
The coordinates of the i-th point (1 \leq i \leq N) are (x_i,y_i).
Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior.
Here, points on the sides of the rectangle are considered to be in the interior.
Find the minimum possible area of such a rectangle.

Constraints

  • 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)
  • All input values are integers. (Added at 21:50 JST)

Input

Input is given from Standard Input in the following format:

N K  
x_1 y_1
:  
x_{N} y_{N}

Output

Print the minimum possible area of a rectangle that satisfies the condition.


Sample Input 1

4 4
1 4
3 3
6 2
8 1

Sample Output 1

21

One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1), (8,1), (1,4) and (8,4).
Its area is (8-1) × (4-1) = 21.


Sample Input 2

4 2
0 0
1 1
2 2
3 3

Sample Output 2

1

Sample Input 3

4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

Sample Output 3

3999999996000000001

Watch out for integer overflows.