레이저 센서

정밀 측정 업체가 레이저로 멀리 떨어진 물체의 변화를 재는 장치를 여러 대 사서 서로 다른 장소에 설치했다. 장치마다 레이저 센서가 두 개 있고 센서 하나가 물체 하나를 재므로, 장치 한 대가 물체 두 개를 동시에 잰다. 서로 다른 두 장치에서 나온 레이저 빛이 만나면 서로 간섭해 측정 오류가 생기므로, 레이저 빛이 서로 교차하지 않게 구성한다.

설치한 장치의 위치를 평면 위의 파란점으로, 측정할 물체의 위치를 빨간점으로 나타내면 문제는 다음과 같다.

평면에 파란점 $N$개와 빨간점 $2N$개가 있다. 다음 세 조건을 모두 만족하도록 점을 선분으로 이은 것을 연결 구성이라고 하자.

• 파란점은 각각 빨간점 두 개와 선분으로 이어진다.
• 빨간점은 각각 파란점 하나와 선분으로 이어진다.
• 어떤 두 선분도 서로 교차하지 않는다.

그림의 (A)에는 파란점 3개와 빨간점 6개가 있다. 1번 파란점은 1번과 4번 빨간점에, 2번 파란점은 2번과 5번 빨간점에, 3번 파란점은 3번과 6번 빨간점에 이어져 있고 어떤 두 선분도 교차하지 않으므로 (A)는 연결 구성이다. (B)는 같은 점집합의 또 다른 연결 구성이다. 즉 입력 하나에 연결 구성이 여러 개 있을 수 있다. (C)에서는 1번 파란점과 3번 빨간점을 잇는 선분이 3번 파란점과 2번 빨간점을 잇는 선분과 교차하므로 (C)는 연결 구성이 아니다.

입력 하나에 연결 구성이 여러 개 있을 수 있으므로, 출력에 적힌 절차가 만드는 연결 구성 하나를 출력한다.

첫째 줄에 파란점의 개수 $N$이 주어진다 ($1 \le N \le 1{,}000$). 다음 $N$개 줄 가운데 $i$번째 줄에 $i$번 파란점의 x좌표와 y좌표가 주어진다. 이어지는 $2N$개 줄 가운데 $j$번째 줄에 $j$번 빨간점의 x좌표와 y좌표가 주어진다. 좌표는 모두 $-10^8$ 이상 $10^8$ 이하의 정수이다. 주어진 점 가운데 어떤 세 점도 한 직선 위에 있지 않다.

$N$개 줄을 출력한다. $i$번째 줄에는 $i$번 파란점과 이어진 두 빨간점의 번호를 작은 수부터 공백 하나로 구분해 출력한다.

연결 구성이 여러 개일 수 있으므로 다음 절차가 만드는 구성을 출력한다. 이 절차는 필요한 번호를 항상 찾고, 절차가 만드는 연결 구성은 항상 세 조건을 만족한다.

파란점의 값을 $2$, 빨간점의 값을 $-1$이라 하고, 점 집합의 값을 그 집합에 속한 점의 값의 합이라고 하자. 주어진 점 $3N$개의 값은 $0$이다. 주어진 점 $3N$개 전체에 Solve를 실행한다.

Solve($S$), $S$의 값은 $0$이다.

1. $S$가 비어 있으면 멈춘다.
2. $S$에서 y좌표가 가장 작은 점, 그런 점이 여럿이면 그중 x좌표가 가장 작은 점을 $p$라고 하자. $S$의 나머지 점을 $p$에서 그 점으로 향하는 벡터의 각도가 커지는 순서로 $q_1, q_2, \dots, q_m$이라고 하자. 각도는 x축의 양의 방향에서 반시계 방향으로 잰다. 이 각도는 모두 $0$ 이상 $\pi$ 미만이고 서로 같은 값이 없다.
3. $W_0 = 0$, $W_i = W_{i-1} + v_i$라고 하자. $v_i$는 $q_i$의 값이다.
4. $p$가 파란점이면 $W_k = -1$인 가장 작은 번호를 $k$, $W_l = -2$인 가장 작은 번호를 $l$이라고 하자. $p$를 $q_k$, $q_l$과 잇는다. 그다음 $q_1, \dots, q_{k-1}$과 $q_{k+1}, \dots, q_{l-1}$과 $q_{l+1}, \dots, q_m$에 각각 Solve를 실행한다.
5. $p$가 빨간점이면 $W_{k-1} \le 0$인 가장 큰 번호를 $k$라고 하자. $q_k$는 파란점이다. $p$를 $q_k$와 잇는다. $W_{k-1} = -1$이면 Attach($q_1, \dots, q_{k-1}$; $q_k$; $p$)와 Solve($q_{k+1}, \dots, q_m$)을 실행하고, 그렇지 않으면 Solve($q_1, \dots, q_{k-1}$)과 Attach($q_{k+1}, \dots, q_m$; $q_k$; $p$)를 실행한다.

Attach($T$; $c$; $p$), $T$는 비어 있지 않고 값이 $-1$이며, 파란점 $c$는 빨간점 하나를 더 이어야 하고, $p$는 $T$ 밖의 점이다.

1. $T$의 점을 $c$에서 $p$로 향하는 반직선과 $c$에서 그 점으로 향하는 반직선이 $c$에서 이루는 각이 커지는 순서로 $s_1, s_2, \dots, s_t$라고 하자. 이 각은 모두 $0$보다 크고 $\pi$보다 작으며 서로 같은 값이 없다.
2. $V_0 = 0$, $V_i = V_{i-1} + u_i$라고 하자. $u_i$는 $s_i$의 값이다.
3. $V_{j-1} \ge 0$인 가장 큰 번호를 $j$라고 하자. $s_j$는 빨간점이다. $c$를 $s_j$와 잇는다. 그다음 $s_1, \dots, s_{j-1}$과 $s_{j+1}, \dots, s_t$에 각각 Solve를 실행한다.