전방위 세계 일주

이 문제의 저자일 수도 있고 아닐 수도 있는 용감한 세계 여행가 K는 최근 여행을 많이 다녔다. 최근 여행 중 하나에서 그녀는 San Francisco에서 출발해 Frankfurt, Johannesburg, Abu Dhabi, Singapore, Tokyo를 거쳐 다시 San Francisco로 돌아왔다. 이 여행에서 그녀는 모든 자오선에 닿는 닫힌 경로를 따라 이동하여 지구를 일주했다. 다시 말해, 가능한 모든 경도마다 이 경로 위에 그 경도를 갖는 점이 적어도 하나 있다.

하지만 North Pole로 날아간 다음 그 주위를 걸어도 지구를 일주할 수 있고, 이는 특별히 어려워 보이지 않으므로(물론 North Pole로 날아가는 부분은 제외한다), K는 이 여행이 엄청나게 멋진 여행에 해당하는지 확신하지 못한다. 그래서 그녀는 세계 일주를 더 일반화하여 정의하기로 했다. 이 새로운 개념을 전방위 세계 일주라고 한다. 이는 지구를 구라고 가정할 때, 극을 어디에 두더라도 세계 일주가 되는 지구 주위의 닫힌 경로이다. 다시 말해, 전방위 세계 일주는 구의 표면에서 가능한 모든 반구에 닿는 닫힌 경로이다. (반구의 경계에 닿는 것으로 충분하다.) 이와 동등하게, 전방위 세계 일주는 가능한 모든 대원, 즉 구의 표면에서 가능한 가장 큰 지름을 갖는 원과 교차한다.

반지름이 1인 구 위의 N개 점으로 이루어진 수열이 주어진다. 이 점들을 순서대로 연결하는 경로가 전방위 세계 일주인지 확인해야 한다. 이 경로는 연속한 각 점의 쌍을 가능한 가장 짧은 표면 경로를 따라 연결하고, 마지막 점과 첫 번째 점도 같은 방식으로 연결하여 만든다. 연속한 두 점은 어느 쌍도(마지막 점과 첫 번째 점의 쌍을 포함하여) 원점과 일직선상에 있지 않다. (즉, 두 점은 대척점, 곧 극의 반대편에 있는 점이 아니며, 구의 표면에서 같은 점을 나타내지도 않는다.)

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 200. -$10^{6}$ ≤ $X_{i}$ ≤ $10^{6}$, 모든 i에 대해. -$10^{6}$ ≤ $Y_{i}$ ≤ $10^{6}$, 모든 i에 대해. -$10^{6}$ ≤ $Z_{i}$ ≤ $10^{6}$, 모든 i에 대해. 모든 i에 대해 ($X_{i}$, $Y_{i}$, $Z_{i}$)의 값 중 적어도 하나는 ≠ 0. (i + 1 = j) 또는 (i = N - 1이고 j = 0)를 만족하는 모든 i, j에 대해, ($X_{i}$, $Y_{i}$, $Z_{i}$)와 ($X_{j}$, $Y_{j}$, $Z_{j}$) 중 어느 것도 다른 하나의 정수배가 아니다. (마지막 점과 첫 번째 점을 포함하여, 연속한 두 점은 대척점이 아니며 구 위의 같은 점을 나타내지도 않는다.)

소규모 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 60초. 3 ≤ N ≤ 50.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 300초. 3 ≤ N ≤ 5000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 K가 방문한 도시의 수 N이 담긴 한 줄로 시작한다. 다음 N개의 줄에는 각각 세 정수 $X_{i}$, $Y_{i}$, $Z_{i}$가 주어진다. 목록의 i번째 점은 좌표 ($X_{i}$ / sqrt($X_{i}^{2}$ + $Y_{i}^{2}$ + $Z_{i}^{2}$), $Y_{i}$ / sqrt($X_{i}^{2}$ + $Y_{i}^{2}$ + $Z_{i}^{2}$), $Z_{i}$ / sqrt($X_{i}^{2}$ + $Y_{i}^{2}$ + $Z_{i}^{2}$))로 주어진다.

각 테스트 케이스마다 Case #x: y를 담은 한 줄을 출력한다. 여기서 x는 케이스 번호이고, y는 경로가 전방위 세계 일주인지 여부에 따라 YES 또는 NO이다.

예제 케이스 #1에서 세 점은 구의 한 팔분공간에 해당하는 표면의 점들이며, 경로는 그 팔분공간의 경계를 따라간다. 이 경로와 전혀 겹치지 않는 반구가 많이 있다.

예제 케이스 #2에서 여덟 점은 구에 내접한 정육면체의 꼭짓점들이다. 어떤 반구든 이 경로의 적어도 일부를 포함한다. 모든 값을 5로 나누면 동등한 케이스(같은 점들의 집합을 갖는 케이스)가 된다는 점에 유의한다.

예제 케이스 #3에서 경로 자체가 대원이므로, 다른 모든 대원은 반드시 어딘가에서 이 경로와 교차한다.

예제 케이스 #4에서는 예제 케이스 #3와 같은 세 점을 사용하지만, 처음 두 점을 각각 두 번 방문한다. 하나의 케이스에 같은 점을 여러 방식으로 표현한 값이 포함될 수 있고, 경로에 같은 점이나 연결이 두 번 이상 포함될 수 있다는 점에 유의한다.