¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#10410
Calificación en espera

울타리 설계 60s 1024MB

Problemas

당신은 울타리 시공 회사의 임시 직원으로 고용되어, 어떤 들판의 울타리(fence) 설계를 마무리하는 일을 맡았다. 각 울타리는 두 기둥(pole) 사이를 잇는 하나의 직선 구간이어야 한다. 각 기둥은 평면 위의 한 점을 차지하며, 각 기둥의 위치는 고정되어 있다. 어떤 세 기둥도 한 직선 위에 놓여 있지 않다. 울타리들은 서로 교차할 수 없으며, 단 끝점(기둥)에서 만나는 것은 허용된다.

이 설계는 다른 사람이 시작했지만, 울타리를 정확히 두 개 추가한 뒤 프로젝트를 그만두었다. 당신은 그 설계를 완성해야 한다. 상사와 고객에게 깊은 인상을 남기기 위해, 울타리의 길이와 무관하게 가능한 한 많은 울타리를 포함하는 설계를 만들고 싶다.

기둥들의 위치와 이미 설치된 울타리 두 개가 주어질 때, (기존 울타리와 새 울타리를 모두 포함해) 어떤 두 울타리도 끝점에서만 만날 수 있고 그 외에는 교차하지 않도록 하면서 추가할 수 있는 울타리의 개수를 최대화하는 방법을 찾아라.


Entrada

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 정수 \mathbf{N}이 주어진 한 줄로 시작하며, 이는 기둥의 개수이다. 그 다음 \mathbf{N}줄이 이어지며, 이 중 i번째 줄에는 두 정수 \mathbf{X_i}, \mathbf{Y_i}가 주어진다. 이는 i번째 기둥의 위치의 X좌표와 Y좌표이다. 각 테스트 케이스의 마지막 두 줄은 이미 존재하는 울타리 두 개를 나타낸다. 각 줄에는 두 정수 \mathbf{P_k}, \mathbf{Q_k}가 주어지며, k번째 기존 울타리가 \mathbf{P_k}번째 기둥과 \mathbf{Q_k}번째 기둥을 잇는다는 뜻이다. (기둥 번호는 1부터 시작한다.)


Salida

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 설계에 추가할 수 있는 울타리의 최대 개수(기존 울타리는 제외)이다. 그 다음 y줄을 더 출력하라. 각 줄에는 서로 다른 두 정수 i, j(둘 다 1 이상 \mathbf{N} 이하)가 들어 있어야 하며, 이는 i번째 기둥과 j번째 기둥을 잇는 울타리 하나를 의미한다. 기존 울타리 2개와 당신이 추가한 y개의 울타리, 총 y+2개의 울타리 중 어떤 두 울타리도 끝점에서만 만날 수 있고 그 외에는 교차하거나 겹치면 안 된다.


Ejemplo 

2
4
0 0
0 1
1 1
1 0
1 2
3 4
5
0 0
0 1
1 1
1 0
2 3
1 2
3 5
Case #1: 3
1 4
2 3
4 2
Case #2: 6
5 4
2 4
5 2
1 4
4 3
3 2
다음 그림은 주어진 샘플의 기둥과 울타리를 보여준다. 더 굵은 파란 선이 기존 울타리이고, 나머지는 샘플 출력에서 보여준 것처럼 최대한 많은 울타리를 추가하는 방법을 나타낸다.

Fuente

GCJ 2021r3 C

Debes iniciar sesión para escribir código.