eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Partition

Partition

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. \InputFile Input will consist of multiple test cases. Each test case begins with a line with \textbf{3} space-separated integers \textbf{N}, \textbf{W}, and \textbf{H}, denoting the number of trees, the width of the forest, and the height of the forest, respectively. The forest's four corners are \textbf{(0, 0)}, \textbf{(W, 0)}, \textbf{(0, H)}, and \textbf{(W, H)}. Following this line are \textbf{N} lines each with a pair of space-separated integers \textbf{x_i} and \textbf{y_i} denoting the coordinates of the \textbf{i}^th tree. Furthermore, \begin{itemize} \item \textbf{2} ≤ \textbf{N} ≤ \textbf{50000}, \textbf{2} ≤ \textbf{W} ≤ \textbf{10000}, \textbf{2} ≤ \textbf{H} ≤ \textbf{10000}, \textbf{N} is even, \textbf{W} and \textbf{H} are not both even. \item \textbf{0} < \textbf{x_i} < \textbf{W}, \textbf{0} < \textbf{y_i} < \textbf{H} for all \textbf{i}. All locations of trees are distinct. \end{itemize} Input will be terminated with a case where \textbf{N = W = H = 0}, which should not be processed. \OutputFile For each test case, print out \textbf{N=2} lines. On each line, print two space-separated integers \textbf{x_i} and \textbf{y_i}, denoting the coordinates of the \textbf{i}^th tree in the half of the forest that is to be shepherded by Treebeard.
Ліміт часу 5 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
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
Вихідні дані #1
3 3
1 5
2 5
5 1
5 2