当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6640:Support or Not

题目描述
There are $n$ spheres in 3D-space, labeled by $1,2,\dots,n$. The $i$-th sphere's center is at $(x_i,y_i,z_i)$, and the radius of it is $r_i$.

Let's denote the distance between the $i$-th sphere and the $j$-th sphere $d(i,j)$ as

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

That means choosing two points $P$ and $Q$, where $P$ is on the $i$-th sphere's surface or inside it, $Q$ is on the $j$-th sphere's surface or inside it, and minimize the Euclidean distance bewteen $P$ and $Q$.

There are $\frac{n(n-1)}{2}$ pairs of $i,j(1\leq i<j\leq n)$, please find the $k$-th smallest values among these $d(i,j)$.
输入解释
The first line of the input contains an integer $T(1\leq T\leq 3)$, denoting the number of test cases.

In each test case, there are two integers $n,k(2\leq n\leq 100000,1\leq k\leq\min(300,\frac{n(n-1)}{2}))$ in the first line, denoting the number of spheres and the parameter $k$.

For the next $n$ lines, each line contains four integers $x_i,y_i,z_i,r_i(0\leq x_i,y_i,z_i\leq 10^6,1\leq r_i\leq 10^6)$, denoting each sphere.
输出解释
For each test case, print $k$ lines, each line contains an integer, denoting the $k$-th smallest values among these $d(i,j)$. You should print them in non-decreasing order. To avoid precision error, print $\lceil d(i,j)\rceil$ instead. For example, $\lceil 5\rceil=5$, and $\lceil 5.1\rceil=6$.
输入样例
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
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6640

最后修改于 2020-10-25T23:33:04+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
6000/6000MS(Java/Others) 524288/524288K(Java/Others)