CF1651D Nearest Excluded Points

给定平面上的 $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]$ 的范围。可以证明，任何最优解都满足这个范围。 如果有多个答案，可以输出其中任意一个。

由 ChatGPT 4.1 翻译