ACM contest 大学生程序设计竞赛 Question 4 求解！！！

Question

PROBLEM 4 − ORCHARDSJohn wants to fence in all his trees, and happily his friend Bill has a fence building
company.Being a good friend, Bill has proposed to build the required fences for free,
provided that costs are kept under control. Specifically, Bill agrees to build fences
for up to three square paddocks, with sides parallel to the coordinate axes, with
the condition that the side of the largest paddock(s) is as small as possible.All paddocks must be square (have equal length sides) and paddocks must
enclose all trees, considering trees as distinct points in the plane. The paddocks
may intersect, or overlap on their borders, or even have 0–length sides, and a
tree on a fence is considered enclosed.A paddock may enclose only one tree, in which case its side length is 0. For
example, the following diagram shows how three paddocks, of side lengths 1, 2,
and 0, can be used to enclose 6 trees....中间有个提示图贴不上来，不过看了上面问题可以画出来！就类似五子棋的table一样。Your task is to find the minimum side of the largest paddock(s) that Bill needs to
build. In the above diagram, the minimum such side is 2.INPUT FORMAT
Input for this problem consists of a sequence of one or more scenarios. Each
scenario is described by several lines.o The first line contains, in order, the label of the scenario, a number, s, 1 ≤ s
≤ 100, followed by the number of the trees, n, 1 ≤ n ≤ 1000, separated by a
single space.o The first line will be followed by one or more lines containing 2×n integers,
separated by single spaces or newlines, giving, in order, the coordinates of
the trees, x before y, 0 ≤ x, y ≤ 1000000.The input will be terminated by a line consisting of two zero numbers (0),
separated by a single space. This line should not be processed.SAMPLE INPUT:
1 6
1 0 2 1 3 2 4 3 4 4 6 0
2 5
1 0 2 1 3
2 5 4 6 0
3 1
1 1
4 2
1 0 5 5
0 0OUTPUT FORMAT
Output will be a sequence of lines, one for each input scenario. Each line will
contain in order the scenario label, followed by the minimum side of the largest
paddock(s) required by the problem, separated by a single space.SAMPLE OUTPUT:
1 2
2 2
3 0
4 0Attention, for this program, input lines may contain up to 2000 characters each!