2517: 为了虫群
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：3
题目描述
小 Y 率领的人类的部队已经踏上了异虫的基地——查尔星。 作为异虫的首脑,你
决定派出爆虫来迎击人类的部队。
爆虫身上长有充满酸液的囊。 当它接近敌人时,会触发体内的不稳定化学物质进
行反应,将自身引爆,向外泼洒强酸。 自爆会摧毁爆虫,但同时也会对半径 R 之内(包
括距离为 R 的点)的敌人造成大量伤害。
你观察到,人类有 n 名陆战队员,站成一条直线。 每个陆战队员的坐标是 xi。
你有 k 个爆虫。 爆虫的酸液会对陆战队员造成巨大伤害,将其瞬间消灭。 你可以把每
只爆虫安排在直线上的任意位置,然后引爆,从而消灭距离该爆虫不超过 R 的所有陆战
队员。
为了消灭所有 n 个陆战队员,你需要计算,爆虫的爆炸半径 R 至少要多少。
输入
输入共两行。第一行是用空格隔开的两个整数,n 和 k。1≤k<n≤100,000。
第二行是用空格隔开的 n 个实数,表示每个陆战队员的坐标 xi。 −10^7≤xi≤10^7。
所有坐标按升序给出。(可能存在某个位置有多名队员)
输出
输出共一行。爆虫的最小爆炸半径 R。保留 6 位小数。
样例输入 复制
5 2
-10.0 -6.0 10 11 15样例输出 复制
2.500000提示
将第一只爆虫放在坐标−8 处,第二只爆虫放在坐标 12.5 处。这时,只要爆炸半径
为 2.5,就能消灭所有陆战队员。
30%
n<=50;
100%
1<=k<n<=100,000, -10^7<=xi<=10^7。