#P16369. [2026年山东第二轮集训]如何变得善良

[2026年山东第二轮集训]如何变得善良

题目描述

三维空间中有 nn 个球体,编号为 1,2,…,n1,2,\ldots,n。第 ii 个球体 SiS_i 的中心位于

(xi,yi,zi),(x_i,y_i,z_i),

半径为 rir_i。

设 d(i,j)d(i,j) 为 SiS_i 和 SjS_j 的最短间距:分别从 SiS_i 与 SjS_j 的表面或内部选择一点 PP 和一点 QQ,d(i,j)d(i,j) 是 P,QP,Q 在三维空间中的最小欧几里得距离。

将所有满足 1≤i<j≤n1\le i<j\le n 的 d(i,j)d(i,j) 排成一列,请求出其中最小的 kk 个值。

输入格式

第一行包含两个正整数 n,kn,k,含义如题目描述所述。

接下来 nn 行,每行包含四个整数 xi,yi,zi,rix_i,y_i,z_i,r_i,表示第 ii 个球体的球心坐标和半径。

输出格式

输出一行 kk 个非负整数,表示最小的 kk 个 d(i,j)d(i,j),按照不降顺序输出。

为了避免精度误差,你只需要输出

⌈d(i,j)⌉,\left\lceil d(i,j)\right\rceil,

即 d(i,j)d(i,j) 向上取整后的值。

样例 1

输入

4 6
0 0 0 1
0 3 2 2
3 2 1 1
1 1 2 2

输出

0 0 0 1 1 2

数据范围

对于全部测试数据:

2≤n≤2×105,2\le n\le 2\times 10^5, 1≤k≤min⁡(300,(n2)),1\le k\le \min\left(300,\binom n2\right), 0≤xi,yi,zi≤106,1≤ri≤106.0\le x_i,y_i,z_i\le 10^6,\qquad 1\le r_i\le 10^6.
子任务编号 n≤n\le k≤k\le 特殊性质 分值
1 20002000 300300 无 16
2 2×1052\times 10^5 11
3 2020
4 300300 xi,yi,zi≤1000x_i,y_i,z_i\le 1000
5 所有 xi,yi,zix_i,y_i,z_i 随机生成
6 无 20