페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10375

한 번의 웜홀 30s 1024MB

문제

당신은 은하 간 초공간 골프(hyperspace golf) 대회에 참가하고 있으며, 결승 라운드까지 진출했다! 당신은 정말로 우승하고 싶어서, 승리 전략을 준비하려 한다.

초공간 골프는 일반 골프와 마찬가지로, 클럽으로 공을 쳐서 당신이 선택한 방향으로 보낸다. 초공간 골프의 필드는 2차원 평면이며, 점들이 각기 다른 홀을 나타낸다. 공도 점으로 표현되며, 공의 시작 위치는 어떤 홀과도 같은 위치가 아니기만 하면 당신이 정할 수 있다.

초공간 골프에서는 일부 홀 쌍을 서로 연결해 웜홀(wormhole)로 만들 수 있다. 각 홀은 일반 홀로 남겨 둘 수도 있고, (자기 자신은 제외하고) 다른 홀 최대 하나와 연결할 수도 있다. 웜홀은 무방향 연결이므로 어느 방향으로든 통과할 수 있다.

환경에 마찰이 없으므로, 당신이 공을 치면 공은 어떤 직선 방향으로 계속 움직이다가 홀에 도달하면 멈추거나(또는 웜홀을 통과) 한다. 공이 닿은 홀을 h라고 하자. h가 다른 홀과 연결되어 있지 않다면 공은 h에서 멈춘다. h가 다른 홀 h'와 연결되어 있다면, 공은 즉시 h'에서 튀어나와(나오면서는 이동 없이) 이전과 같은 방향으로 계속 움직인다.

당신은 각 홀의 위치를 알고 있다. 한 번의 샷으로 접촉할 수 있는 서로 다른 홀의 개수를 최대화하고 싶다. 이를 위해 공의 시작 위치, 공을 보낼 방향, 그리고 (있다면) 어떤 홀 쌍들을 웜홀로 연결할지 선택하려 한다. 공의 시작 위치는 웜홀이 있는 위치(홀의 위치)와 같을 수 없다. 공이 웜홀을 통과할 때에는 들어간 홀과 나온 홀이 모두 총합에 포함된다. 공이 어떤 홀로 들어가거나 어떤 홀에서 나오거나(또는 둘 다) 여러 번 일어나더라도, 각 홀은 한 번만 센다. 공이 어떤 홀에서 멈춘다면 그 홀도 총합에 포함된다.


입력

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 전체 홀의 수 N이 주어진 한 줄로 시작한다. 이어서 N줄이 주어지며, 각 줄에는 두 정수 Xi, Yi가 주어진다. 이는 i번째 홀의 X, Y 좌표를 나타낸다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 위에서 설명한 대로 최적으로 선택했을 때 한 번의 샷으로 접촉할 수 있는 서로 다른 홀의 최대 개수이다.


예제 

5
2
0 0
5 5
3
0 0
5 5
5 0
5
0 0
5 5
5 0
3 2
2 4
7
0 0
1 1
2 1
3 1
8 2
11 2
14 2
1
-1000000000 1000000000
Case #1: 2
Case #2: 3
Case #3: 4
Case #4: 7
Case #5: 1
샘플 케이스 #1에서는 두 구멍을 웜홀로 연결하면 공을 어느 쪽에 넣어도 두 구멍을 모두 터치할 수 있다. 웜홀이 없다면 공은 처음 닿은 구멍에 머물기만 하므로, 한 개보다 많은 구멍을 터치하는 것은 불가능함을 유의하라. 샘플 케이스 #2에서는 (0, 0)과 (5, 5)의 구멍을 연결할 수 있다. 예를 들어 (4.9, 5)에서 수평 양의 방향으로 공을 치면 먼저 (5, 5)의 구멍을 터치한다. 그 구멍으로 들어갔다가 (0, 0)에서 나오며, 양의 수평 방향의 이동을 유지한다. 마지막으로 (5, 0)의 구멍을 터치하고 멈춘다(그 구멍과 연결된 웜홀이 없기 때문이다). 샘플 케이스 #3에서는 (0, 0)과 (5, 0)을 한 쌍으로, (3, 2)와 (5, 5)를 또 한 쌍으로 연결할 수 있다. (4, -1)에서 (5, 0)을 향해 공을 치면 (5, 0), (0, 0), (5, 5), (3, 2) 순서로 구멍을 터치한다. 샘플 케이스 #4에서는 (0, 0)과 (1, 1), (2, 1)과 (11, 2), (8, 2)와 (14, 2)를 각각 쌍으로 연결할 수 있다. (-1, 0)에서 (0, 0)을 향해 공을 치면 다음 순서로 구멍을 터치한다: (0, 0), (1, 1), (2, 1), (11, 2), (14, 2), (8, 2), (11, 2), (2, 1), (3, 1). (11, 2)와 (2, 1)은 두 번 터치되지만, 문제는 서로 다른 구멍의 개수를 묻기 때문에 각 1번만 센다는 점을 유의하라. 샘플 케이스 #5에서는 구멍이 하나뿐이므로 웜홀을 고려할 필요 없이 공을 그 구멍에 넣으면 된다. (참고로, 시작 위치는 구멍 좌표의 허용 범위를 벗어나도 아무 것이나 선택할 수 있다.)

출처

GCJ 2020r2 C

로그인해야 코드를 작성할 수 있어요.