2481. Square Fields

单点时限: 2.0 sec

内存限制: 256 MB

You are given n points in the plane. You are asked to cover these points with k squares.

The squares must all be the same size, and their edges must all be parallel to the coordinate axes.

A point is covered by a square if it lies inside the square, or on an edge of the square.

Squares can overlap.

Find the minimum length for the squares’ edges such that you can cover the n points with k squares.


The first line of input gives the number of cases, N(1 ≤ N ≤ 10). N test cases follow. The first line of each test contains two positive integers n and k(1 ≤ k < n ≤ 15). Each of the next n lines contains a point as two integers separated by exactly one space. No point will occur more than once within a test case.

The points’ coordinates are non-negative integers smaller than 64000.


For each test case, you should output one line containing “Case #X: Y” (quotes for clarity), where X is the number of the test case, starting from 1, and Y is the minimum length for the squares’ edges for that test case.


5 2
1 1
2 2
3 3
6 6
7 8
3 2
3 3
3 6
6 9
Case #1: 2
Case #2: 3

1 人解决,2 人已尝试。

1 份提交通过,共有 3 份提交。

9.7 EMB 奖励。

创建: 15 年,3 月前.

修改: 6 年,10 月前.

最后提交: 3 年,7 月前.

来源: GCJ 2008