Omnicircumnavigation (Large)

K travels a lot. On one recent trip she went from San Francisco to Frankfurt to Johannesburg to Abu Dhabi to Singapore to Tokyo and back to San Francisco. On that trip she circumnavigated the Earth along a closed path that touches every meridian. For every possible longitude there is at least one point of the path at that longitude.

K is not sure that such a trip deserves much credit, since flying to the North Pole and then walking around it would also count. So she came up with a more general definition. An omnicircumnavigation is a closed path around the Earth, which we assume to be a sphere, that is a circumnavigation no matter where the poles are placed. In other words, an omnicircumnavigation is a closed path on the surface of a sphere that touches every possible hemisphere. Touching the edge of a hemisphere is enough. Stated another way, an omnicircumnavigation intersects every possible great circle, a circle of greatest possible diameter on the surface of a sphere.

You are given a sequence of $N$ points on a sphere of radius 1. Decide whether the path that connects those points in order is an omnicircumnavigation. The path connects each pair of successive points along the shortest surface route, and connects the last point to the first one in the same way. No two successive points, including the pair formed by the last point and the first point, are collinear with the origin. They are not antipodes, and they do not represent the same point on the surface of the sphere.

The first line of the input gives the number of test cases, $T$. The first line of each test case contains $N$, the number of places K visited. Each of the next $N$ lines contains three integers $X_i$, $Y_i$ and $Z_i$. The $i$-th point in the list is the point $\left(\dfrac{X_i}{\sqrt{X_i^2 + Y_i^2 + Z_i^2}}, \dfrac{Y_i}{\sqrt{X_i^2 + Y_i^2 + Z_i^2}}, \dfrac{Z_i}{\sqrt{X_i^2 + Y_i^2 + Z_i^2}}\right)$ on the sphere.

Limits

• $1 \le T \le 200$
• $3 \le N \le 5000$
• $-10^6 \le X_i \le 10^6$ for all $i$
• $-10^6 \le Y_i \le 10^6$ for all $i$
• $-10^6 \le Z_i \le 10^6$ for all $i$
• At least one of $X_i$, $Y_i$, $Z_i$ is nonzero, for all $i$.
• For two successive points on the path, neither one is a constant multiple of the other. The last point and the first point count as successive. That is, two successive points are never antipodes and never the same point on the sphere.

For each test case, output one line containing Case #x: y, where $x$ is the test case number and $y$ is YES if the route is an omnicircumnavigation and NO if it is not.

In the first test case of the example input, the three points are the corners of one octant of the sphere, and the path traces the border of that octant. Many hemispheres do not meet that path at all.

In the second test case, the eight points are the corners of a cube inscribed in the sphere. Every hemisphere contains some part of that path. Dividing all values by 5 produces the same set of points, so the answer stays the same.

In the third test case, the path is itself a great circle, so every other great circle meets it somewhere.

The fourth test case uses the same three points as the third one, except that the first two points are visited twice each. A test case may list the same point more than once, and a path may cover the same points or the same arcs more than once.