P3775 [CTSC2017] Projection

None.

换一个角度看，世界可能就不同。 —— 小强 k 维空间中有 n 个黑点与 n 个白点。我们为每一个黑点确定一个互不相同的对应的白点，这样一共有 n! 种对应方法。我们定义这 n 个黑点与 n 个白点之间的 “移动距离”为，在所有的对应方法中，对应的黑点与白点之间的 n 个欧几里德距离的和的最小值。 例如; 考虑一维中的三个黑点 {1,5,6} 与三个白点 {2,3,4}，那么它们之间的移动距离为; |1 − 2| + |5 − 3| + |6 − 4| = 4。你可以验证一下这确实是距离和最小的一种对应方法。 你得到了三维空间中的 n 个黑点与 n 个白点。你想把它们投影到一个 k(1 ≤ k ≤ 2)维子空间上。一维子空间就是三维空间中的一条直线，二维子空间则是三维空间中的一个平面。一个点在一个子空间中的投影点就是这个子空间中距离它最近的点。例如，(0, 0, 0), (1, 1, 0), (1, 0, 0), (0, 1, 0) 这四个点投影到 x − y = 0,z = 0 这条直线上之后，得到的投影点是 (0, 0, 0), (1, 1, 0), (0;5, 0;5, 0), (0;5, 0;5, 0)。 你希望这 n 个黑点和 n 个白点投影到这个 k 维子空间之后的移动距离最大。请你计算这个最大值除以 n。

每个测试文件中可能有多个测试用例，每个测试用例的格式如下： 第一行两个数 n 和 k，表示点数以及降到的维度。 后面 2n 行，每行三个数，表示点的坐标。 文件最后有一行包含两个数 −1 − 1。

For each test case in the file, output one number on a single line (its length should not exceed 30), representing the result. Your answer will be considered correct if its relative error does not exceed $10^{-7}$ compared to the reference answer. You will receive points for a test file only if all test cases in that file are answered correctly.

- For 30% of the testdata, $k = 1$, $n \le 1000$, and all points have $z = 0$. At most one test case appears in a file. - For another 40% of the testdata, $k = 1$, $n \le 1000$, and all point coordinates are independently and uniformly generated in $[-1, 1]$. At most ten test cases appear in a file. - For the remaining 30% of the testdata, $k = 2$, $n \le 20$, and all point coordinates are independently and uniformly generated in $[-1, 1]$. At most ten test cases appear in a file. - For 100% of the testdata, all coordinates lie in $[-1, 1]$, and the answer is at least $0.01$. Translated by ChatGPT 5