#P3681. Finding the Rectangle
Finding the Rectangle
Description
Given N point on the x-y coordinates, you are to find the rectangle of the smallest area which covers no less than M points. The coordinates of the four vertices must be integers and the sides must be parallel to the axes. If one point lies on the sides of the rectangle, it is not considered as being covered.
Input
The first line of input is the number of test case.
The first line of each test case contains two integers, N and M (1 ≤ M ≤ N ≤ 200).
The next N line each contain two integers xi, yi (1 ≤ xi, yi ≤ 10,000) describing the points.
There is a blank line before each test case.
Output
For each test case output the smallest area in a separate line.
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
Source
POJ Founder Monthly Contest – 2008.07.27, windy7926778
</p>