18592번 - Support or Not 다국어

문제

There are \(n\) spheres in the three-dimensional space, labeled by 1, 2, . . . , \(n\). The center of the \(i\)-th sphere is at point \((x_i, y_i, z_i)\), and its radius is \(r_i\).

Let us denote the distance between spheres \(i\) and \(j\) as

\[d(i,j) = \max{\left(0, \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2 + (z_i-z_j)^2} - r_i - r_j\right)}\text{.}\]

That means choosing two points \(P\) and \(Q\), where \(P\) is inside or on the surface of sphere \(i\) and \(Q\) is inside or on the surface of sphere \(j\), and minimizing the Euclidean distance between \(P\) and \(Q\).

There are \(\frac{n(n−1)}{2}\) pairs \((i, j)\) such that \(1 \le i < j \le n\). Please find the smallest \(k\) values among the values of \(d(i, j)\) for all these pairs.

입력

The first line of the input contains an integer \(T\) (\(1 \le T \le 3\)), denoting the number of test cases.

Each test case starts with a single line containing two integers \(n\) and \(k\) (\(2 \le n \le 100 000, 1 \le k \le \min{(300, \frac{n(n−1)}{2})}\)), denoting the number of spheres and the parameter \(k\).

Each of the next n lines contains four integers, \(x_i\), \(y_i\), \(z_i\), and \(r_i\) (\(0 \le x_i, y_i, z_i \le 10^6, 1 \le r_i \le 10^6\)), describing \(i\)-th sphere.

출력

For each test case, print \(k\) lines, each line containing a single integer: the smallest \(k\) values among \(d(i, j)\) in non-decreasing order. To avoid precision error, print the values of \(\lceil d(i, j)\rceil\): the values of the respective \(d(i, j)\) rounded up. For example, \(\lceil5\rceil = 5\), and \(\lceil5.1\rceil = 6\).

제한

힌트