Вам даны $$$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]$$$. Можно показать, что любой оптимальный ответ удовлетворяет заданным ограничениям.
Если существует несколько возможных ответов, вы можете вывести любой из них.
6 2 2 1 2 2 1 3 2 2 3 5 5
1 1 1 1 2 0 3 1 2 4 5 4
8 4 4 2 4 2 2 2 3 1 4 4 2 1 3 3 3
4 3 2 5 2 1 2 5 1 5 4 1 1 2 3 2
Название |
---|