Problem Description

Looking at the world from a different angle can make a difference. — Xiaoqiang

In a k-dimensional space, there are n black points and n white points. We assign each black point a unique corresponding white point, resulting in n! possible assignments. The "movement distance" between these n black points and n white points is defined as the minimum sum of the n Euclidean distances between the corresponding black and white points across all possible assignments.

For example, consider three black points {1, 5, 6} and three white points {2, 3, 4} in one dimension. Their movement distance is |1 − 2| + |5 − 3| + |6 − 4| = 4. You can verify that this is indeed the minimum sum of distances.

You are given n black points and n white points in a three-dimensional space. You want to project them onto a k-dimensional (1 ≤ k ≤ 2) subspace. A one-dimensional subspace is a line in the three-dimensional space, and a two-dimensional subspace is a plane in the three-dimensional space. The projection of a point onto a subspace is the closest point in that subspace to the original point. For example, the points (0, 0, 0), (1, 1, 0), (1, 0, 0), (0, 1, 0) projected onto the line x − y = 0, z = 0 result in the projected points (0, 0, 0), (1, 1, 0), (0.5, 0.5, 0), (0.5, 0.5, 0).

You want the movement distance of the n black and n white points after projection onto this k-dimensional subspace to be maximized. Calculate this maximum value divided by n.

Input Format

Each test file may contain multiple test cases. Each test case is formatted as follows:

The first line contains two numbers n and k, representing the number of points and the dimension to which they are reduced.

The following 2n lines, each containing three numbers, represent the coordinates of the points.

The file ends with a line containing two numbers -1 -1.

Output Format

For each test case in the file, output one line containing a number (length not exceeding 30), representing the result.

Your answer is considered correct if the relative error from the reference answer does not exceed 10^−7.

Only when all results for all test cases in a file are correct will you receive the score for that file.

Sample Input and Output

Sample Input #1

2 1
0 0 0
1 1 0
0 1 0
1 0 0
-1 -1

Sample Output #1

0.70710678118655

Sample Input #2

4 2
0 0 0
0 1 1
1 0 1
1 1 0
0 0 1
0 1 0
1 0 0
1 1 1
-1 -1

Sample Output #2

0.73883404559321

Notes

For 30% of the data, k = 1, n ≤ 1000, and all points have z coordinates of 0. A file contains at most one test case.

For another 40% of the data, k = 1, n ≤ 1000, and all points' coordinates are uniformly and independently randomly generated within the range [−1, 1]. A file contains at most ten test cases.

For another 30% of the data, k = 2, n ≤ 20, and all points' coordinates are uniformly and independently randomly generated within the range [−1, 1]. A file contains at most ten test cases.

For 100% of the data, the coordinates of the points are within the range −1 to +1, and the answer is not less than 0.01.

见题面 Input 部分

见题面 Output 部分