Laser Sensors

A precision measurement company bought several devices that measure the movement of a distant object with a laser and installed them at different places. Every device carries two laser sensors and one sensor measures one object, so a single device measures two objects at the same time. Laser beams sent from two different devices interfere with each other where they meet, and that interference produces measurement errors, so the beams are arranged so that they never cross.

Draw every installed device as a blue point of the plane and every measured object as a red point. The task becomes the following.

The plane holds $N$ blue points and $2N$ red points. Call a set of segments a linking when it satisfies all three conditions.

• Every blue point is joined to exactly two red points.
• Every red point is joined to exactly one blue point.
• No two segments cross.

Part (A) of the figure holds three blue points and six red points. Blue point 1 is joined to red points 1 and 4, blue point 2 to red points 2 and 5, blue point 3 to red points 3 and 6, and no two segments cross, so (A) is a linking. Part (B) is another linking of the same points, so one input can admit several linkings. In part (C) the segment from blue point 1 to red point 3 crosses the segment from blue point 3 to red point 2, so (C) is not a linking.

One input can admit several linkings, so print the one that the procedure in the output section builds.

The first line holds the number of blue points $N$ ($1 \le N \le 1{,}000$). The $i$-th of the next $N$ lines holds the x coordinate and the y coordinate of blue point $i$. The $j$-th of the following $2N$ lines holds the x coordinate and the y coordinate of red point $j$. Every coordinate is an integer between $-10^8$ and $10^8$. No three of the given points lie on one line.

Print $N$ lines. Line $i$ holds the numbers of the two red points joined to blue point $i$, the smaller number first, separated by one space.

Several linkings can exist, so print the one that the procedure below builds. The procedure always finds the index it asks for, and the linking it builds always satisfies the three conditions.

Give every blue point the value $2$ and every red point the value $-1$, and let the value of a set of points be the sum of the values of its points. The $3N$ given points have value $0$. Run Solve on all $3N$ given points.

Solve($S$), where the value of $S$ is $0$:

1. If $S$ is empty, stop.
2. Let $p$ be the point of $S$ with the smallest y coordinate, and among such points the one with the smallest x coordinate. List the other points of $S$ as $q_1, q_2, \dots, q_m$ in increasing order of the angle of the vector that runs from $p$ to the point, measured counterclockwise from the positive direction of the x axis. Every one of these angles is at least $0$ and smaller than $\pi$, and no two of them are equal.
3. Let $W_0 = 0$ and $W_i = W_{i-1} + v_i$, where $v_i$ is the value of $q_i$.
4. If $p$ is blue, let $k$ be the smallest index with $W_k = -1$ and let $l$ be the smallest index with $W_l = -2$. Join $p$ to $q_k$ and to $q_l$. Then run Solve on $q_1, \dots, q_{k-1}$, on $q_{k+1}, \dots, q_{l-1}$, and on $q_{l+1}, \dots, q_m$.
5. If $p$ is red, let $k$ be the largest index with $W_{k-1} \le 0$. The point $q_k$ is blue. Join $p$ to $q_k$. If $W_{k-1} = -1$, run Attach($q_1, \dots, q_{k-1}$; $q_k$; $p$) and Solve($q_{k+1}, \dots, q_m$). Otherwise run Solve($q_1, \dots, q_{k-1}$) and Attach($q_{k+1}, \dots, q_m$; $q_k$; $p$).

Attach($T$; $c$; $p$), where $T$ is not empty and has value $-1$, the blue point $c$ still needs one red point, and $p$ is a point outside $T$:

1. List the points of $T$ as $s_1, s_2, \dots, s_t$ in increasing order of the angle at $c$ between the ray from $c$ to $p$ and the ray from $c$ to the point. Every one of these angles is greater than $0$ and smaller than $\pi$, and no two of them are equal.
2. Let $V_0 = 0$ and $V_i = V_{i-1} + u_i$, where $u_i$ is the value of $s_i$.
3. Let $j$ be the largest index with $V_{j-1} \ge 0$. The point $s_j$ is red. Join $c$ to $s_j$. Then run Solve on $s_1, \dots, s_{j-1}$ and on $s_{j+1}, \dots, s_t$.