← 返回题目
题库练习 Nearest Excluded Points
← 上一题 下一题 →

A14908 | Nearest Excluded Points

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

You are given $n$ distinct points on a plane. The coordinates of the $i$ -th point are $(x_i, y_i)$ .

For each point $i$ , find the nearest (in terms of Manhattan distance) point with integer coordinates that is not among the given $n$ points. If there are multiple such points — you can choose any of them.

The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$ .

输入格式

The first line of the input contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of points in the set.

The next $n$ lines describe points. The $i$ -th of them contains two integers $x_i$ and $y_i$ ( $1 \le x_i, y_i \le 2 \cdot 10^5$ ) — coordinates of the $i$ -th point.

It is guaranteed that all points in the input are distinct.

输出格式

Print $n$ lines. In the $i$ -th line, print the point with integer coordinates that is not among the given $n$ points and is the nearest (in terms of Manhattan distance) to the $i$ -th point from the input.

Output coordinates should be in range $[-10^6; 10^6]$ . It can be shown that any optimal answer meets these constraints.

If there are several answers, you can print any of them.

输入输出样例

输入 #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
C++ 编辑器
输入
输出