Equidistance

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

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

Description

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}$

Input

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.

Output

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}$.

Sample Input

2 1 1 0.0000000000 2 2 1.0000000000 0.0000000000 2.0000000000 0.0000000000

Sample Output

Case #1: 1 1.0000000000 Case #2: 1 1.5000000000 0.8660254038

Hint

liuyiding

Source

2017中国大学生程序设计竞赛-总决赛-重现赛(感谢哈工大)

提交代码