Problem Description

In the Weishe Era, year 2233 AD, humans mastered a new technology: based on principles of quantum mechanics, a cosmic broadcast on the surface of the Earth can transmit signals faster than light to the plane that is tangent to the Earth at the given coordinate point.

After the Universal Gravitation broadcasted the coordinates, it carried the seeds of human civilization, left the Solar System, and flew into the depths of the universe.

In the Black Domain Era of the DX3906 galaxy, year 3333 AD, the Universal Gravitation found a huge X galaxy, several light-years in diameter. There are 3 planets suitable for human habitation, located in different corners of the X galaxy. After discussion, some members of the Universal Gravitation chose to stay and settle on these three planets.

For the settled humans, real-time communication is necessary, so the device invented 1100 years ago becomes useful again. Clearly, the three planets can communicate with each other if and only if the working tangent planes of the three cosmic broadcasts completely coincide.

Now, the planet governor Amoeba found you, who are good at programming, and hopes you can compute all possible plans that can establish cosmic broadcasts.

After taking this task, you said to yourself, “This is easy, I can finish it in minutes with ygg,” but the mind-reading Amoeba immediately called you back and told you earnestly that human civilization must continue, so you should also solve the station-building plan for $K$ planets in $K$-dimensional space. The governor did not make it too hard: you only need to handle $K\le10$, because the universe plus the time dimension is $11$-dimensional.

After you finished the program in 3 minutes, Amoeba took a look and gave you a two-dimensional foil—because you did not consider this case in your program.

Given the coordinate dimension $K\ge2$, and $K$ balls in $K$-dimensional coordinates (they may degenerate into points, i.e. the radius can be zero), find all common tangent hyperplanes of these $K$ balls.

The testdata guarantees that there will be no case with no solution or infinitely many solutions, but it does not guarantee that all balls are disjoint.

Here are some definitions:

• Distance: In $K$-dimensional space, given two points $A(a_0,a_1,...,a_{K-1})$ and $B(b_0,b_1,...,b_{K-1})$, the distance between them is $|AB|=\sqrt{\sum_{i=0}^{K-1}(a_i-b_i)^2}$.

• Ball: In $K$-dimensional space, the set of points whose distance to a fixed point $A$ is a constant $r$. Point $A$ is called the center, and $r$ is the radius of the ball.

  When $K=2$, this is the circle you learned in middle school.

• Hyperplane: The set of points whose distances to two points $A$ and $B$ in $K$-dimensional space are equal. In $K$-dimensional space, the dimension of a hyperplane is $K-1$.

  When $K=2$, this is the line (perpendicular bisector) you learned in middle school.

• Tangent hyperplane of a ball: A hyperplane $P$ that has exactly one intersection point with ball $A$.

• Common tangent hyperplane of balls: A hyperplane $P$ that is a tangent hyperplane of all balls.

Input Format

This is an output-only problem. There are 8 input files, named 1.in to 8.in.

Each test point contains multiple datasets. For each test point:

• The first line: the number of datasets $T$ in this test point, and it is guaranteed that $T\le10$.
• For each dataset:
  • The first line: the coordinate dimension $K$, and it is guaranteed that $2\le K\le10$.
  • The next $K$ lines: each line contains $K+1$ real numbers. The first $K$ numbers on the $i$-th line are the coordinates of the center of the $i$-th ball, and the $(K+1)$-th number is the radius of the $i$-th ball.

Output Format

For each input dataset, you need to submit the corresponding output files 1.out to 8.out.

For each dataset in each test point:

• The first line contains a positive integer $S$, meaning that you found $S$ sets of tangent hyperplanes for this dataset. If you do not find any solution, be sure to output $0$, otherwise it will affect the scoring of subsequent datasets, and the consequences are at the contestant's own risk.
• The next $S\times K$ lines: each line contains $K$ decimal numbers. For the line number $S(i-1)+j$ among them, it represents, in the $i$-th solution you output, the tangent point coordinates on the $j$-th ball corresponding to the input.
• The last line: output a blank line.

At the end of the output file, you may add any content, which will not affect your score. We suggest writing something meaningful here (such as a brief method) so that we can do statistical analysis after the contest. The size of a single output file must not exceed 4M.

见附加文件中的 0.in

见附加文件中的 0.ans

Hint

Scoring Rules

• The output order of solutions is not required. In one solution, let the output answer be $A(a_0,a_1,...,a_{K-1})$. If there exists a standard answer $B(b_0,b_1,...,b_{K-1})$ such that $\sum_{i=0}^{K-1}|A_iB_i|^2\le10^{-12}$, then this output solution will be judged correct.
• For the same dataset in the same test point, we count the number of common tangent hyperplanes in the standard answers that are matched. Each standard answer is matched at most once. Outputting duplicate common tangent hyperplanes will not cause negative points. The correctness ratio of the $i$-th dataset is the number of matched standard answers divided by the total number of standard answers, denoted as $rate_i$.
• Scoring method for each test point:
  1. If your output format is invalid, or the parameters do not meet the problem requirements, or the number of answers for some dataset exceeds more than twice (excluding twice) the number of standard answers for that dataset, then you get 0 points.
  2. Without violating the above conditions, getting any single solution correct for any dataset gives you at least 1 point; and only if all answers are correct can you get full marks.
  3. Without violating the above conditions, suppose there are $T$ datasets, and $rate_i$ is the correctness ratio for the $i$-th dataset. Let $score$ be the score of this test point. Then $Yourscore=\frac{score}{T}\times\sum_{i=1}^T\sqrt{rate_i}$. It is rounded to the nearest integer under the above rules, i.e. $Yourscore\in[1,score-1]$. The scores of test points are different, as shown in the table below:

Translated by ChatGPT 5