Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Given $M$ points in Euclidean space of dimension N, where the distances between any pair of points is 1.0, how many points can be added that the equidistance restriction still holds?

Print the maximum number of points can be added, and the coordinates of the points. Recall that the distance of two points $(a_1, a_2, . . . , a_N)$ and $(b_1, b_2, . . . , b_N)$ in $N$ dimensional Euclidean space is defined as:

$\sqrt{(a_1-b_1)^2+(a_2-b_2)^2+...+(a_N-b_N)^2}$

Print the maximum number of points can be added, and the coordinates of the points. Recall that the distance of two points $(a_1, a_2, . . . , a_N)$ and $(b_1, b_2, . . . , b_N)$ in $N$ dimensional Euclidean space is defined as:

$\sqrt{(a_1-b_1)^2+(a_2-b_2)^2+...+(a_N-b_N)^2}$

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains two integer $N$ and $M$, indicating the dimension of the Euclidean space and the number of given points. Then follows $M$ lines, each line contains $N$ real numbers indicating the coordinates of the given points. It is guaranteed that the distances between any two given points is 1.0.

$1 \leq T \leq 100$

$1 \leq N \leq 100$

$1 \leq M$

The coordinates’ absolute value of given points will be strictly less than 100.

The first line of each test case contains two integer $N$ and $M$, indicating the dimension of the Euclidean space and the number of given points. Then follows $M$ lines, each line contains $N$ real numbers indicating the coordinates of the given points. It is guaranteed that the distances between any two given points is 1.0.

$1 \leq T \leq 100$

$1 \leq N \leq 100$

$1 \leq M$

The coordinates’ absolute value of given points will be strictly less than 100.

For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting from 1) and $y$ is the maximum number of points can be added that the equidistance restriction still holds. The following $y$ lines each contains $N$ real numbers specifying the coordinates of the added points. There could be multiple answers to the given input. The answer is accepted as long as for each pair of points, the absolute difference between the distance and 1.0 is smaller than $10^{-8}$.

提交代码