| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 3 | 2 | 2 | 100.000% |
The Coordinate Control Organization has developed an autonomous robot to patrol $N$ distinct important locations on a two-dimensional plane. The $i$-th location has coordinates $(x_i , y_i),ドル and it is guaranteed that no three locations lie on a common line.
To help guide the robot, you may paint some line segments on the ground. Each segment must directly connect two important locations, and no two segments may intersect, except possibly at their endpoints.
The robot will begin its patrol at the midpoint of an arbitrary segment, facing towards one of its endpoints. It will move indefinitely according to the following procedure:
Your task is to paint the segments in such a way that, no matter where the robot starts, it is guaranteed to visit every important location infinitely often. It can be proven that this is always possible.
The first line of input contains a single integer $N$ (2ドル ≤ N ≤ 2,円 000$), the number of important locations.
The next $N$ lines of input each contain two space-separated integers, $x_i$ and $y_i$ ($−10^9 ≤ x_i , y_i ≤ 10^9$), the coordinates of the $i$-th important location.
It is guaranteed that all $N$ important locations are distinct and no three lie on a common line.
On the first line, output a positive integer $M,ドル the number of line segments you paint on the ground.
The next $M$ lines of output should each contain two space-separated integers, $u_i$ and $v_i$ (1ドル ≤ u_i , v_i ≤ N,ドル $u_i \ne v_i$), denoting that you paint a line segment between the $u_i$-th and $v_i$-th important locations.
If there are multiple acceptable answers, output any of them.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 2 | 2ドル ≤ N ≤ 4$ |
| 2 | 4 | 2ドル ≤ N ≤ 8$ |
| 3 | 3 | 3ドル ≤ N$ and the $N$ points are the vertices of a convex polygon in some order. |
| 4 | 7 | The $N$ points form a convex polygon with $N − 1$ vertices plus an additional point inside the polygon. |
| 5 | 9 |
4 0 0 1 1 1 2 2 1
3 1 2 2 3 2 4
The important locations and painted segments are shown in the following figure:
No matter where the robot starts, it will visit every important location infinitely many times. For example, if the robot starts in the middle of the segment between locations 1ドル$ and 2ドル,ドル facing towards location 2ドル,ドル the locations the robot will visit in order are: $$\underline{2, 4, 2, 3, 2, 1}, 2, 4, \dots ,$$ where the underlined portion is repeated infinitely.
8 0 0 0 3 1 1 1 2 4 1 4 2 5 0 5 3
9 1 2 2 4 4 8 8 7 7 5 5 1 3 4 4 5 5 6
The important locations and painted segments are shown in the following figure:
No matter where the robot starts, it will visit every important location infinitely many times.
For example, if the robot starts in the middle of the segment between locations 4ドル$ and 5ドル,ドル facing towards location 5, the locations the robot will visit in order are: $5,ドル \underline{7, 5, 6, 5, 1, 2, 4, 3, 4, 8}, 7, 5, \dots ,$$ where the underlined portion is repeated infinitely. Note that it is not necessary for every segment to be traversed infinitely many times; the solution is valid as long as every location is visited infinitely many times.