← 返回题目列表

Codeforces · 1651/D

D. 最近的排除点

中文机器翻译题面 查看原题

给定平面上 $$$n$$$ 不同的点。第 $$$i$$$ 个点的坐标为 $$$(x_i, y_i)$$$。

对于每个点 $$$i$$$,找到不在给定 $$$n$$$ 点中的整数坐标的最近点(以曼哈顿距离计算)。如果有多个这样的点 - 您可以选择其中任何一个。

两点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的曼哈顿距离为 $$$|x_1 - x_2| + |y_1 - y_2|$$$。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 集合中的点数。

接下来的 $$$n$$$ 行描述点。其中第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le 2 \cdot 10^5$$$) — 第 $$$i$$$ 点的坐标。

保证输入中的所有点都是不同的。

输出

打印 $$$n$$$ 行。在第 $$$i$$$ 行中,打印具有整数坐标的点,该点不在给定的 $$$n$$$ 点中,并且距离输入的第 $$$i$$$ 点最近(就曼哈顿距离而言)。

输出坐标应在 $$$[-10^6 范围内; 10^6]$$$。可以证明任何最优答案都满足这些约束。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

6
2 2
1 2
2 1
3 2
2 3
5 5

输出 #1

1 1
1 1
2 0
3 1
2 4
5 4

输入 #2

8
4 4
2 4
2 2
2 3
1 4
4 2
1 3
3 3

输出 #2

4 3
2 5
2 1
2 5
1 5
4 1
1 2
3 2