OpenJudge

J:Partition

总时间限制:
2000ms
内存限制:
65536kB
描述

The Ents are known as the shepherds of the forest. Treebeard, the oldest living Ent in Middle Earth, needs to determine which trees he is to shepherd and which trees are to be shepherded by his young fellow Ent, Bregalad. They have a rectangular portion of Fangorn forest containing an even number of trees that they need to divide into two pieces using a single straight boundary line. In order to equitably distribute the workload, Treebeard and Bregalad have decided that each of their halves of the forest need to contain equal area and contain an equal number of trees. If a tree lies exactly on the dividing line, then that tree is counted in one or the other of the halves of the forest but not both. Any tree exactly on the dividing line may be assigned to either Treebeard or Bregalad.

输入
Input will consist of multiple test cases. Each test case begins with a line with 3 space-separated integers N, W, and H, denoting the number of trees, the width of the forest, and the height of the forest, respectively. The forest’s four corners are (0, 0), (W, 0), (0, H), and (W, H). Following this line are N lines each with a pair of space-separated integers xi and yi denoting the coordinates of the ith tree. Furthermore,
• 2 <= N <= 50000, 2 <= W <= 10000, 2 <= H <= 10000, N is even, W and H are not both even.
• 0 < xi < W,0 < yi < H for all i. All locations of trees are distinct.
Input will be terminated with a case where N = W = H = 0, which should not be processed.
输出
For each test case, print out N/2 lines. On each line, print two space-separated integers xi and yi, denoting the coordinates of the ith tree in the half of the forest that is to be shepherded by Treebeard.
样例输入
2 5 6
2 3
3 3
4 5 6
1 5
2 5
3 5
4 5
4 10 11
5 1
5 2
5 3
5 4
0 0 0
样例输出
3 3
1 5
2 5
5 1
5 2
全局题号
15072
提交次数
7
尝试人数
1
通过人数
0