← 返回题目列表

Codeforces · 50/D

D. 轰炸

中文机器翻译题面 查看原题

指挥官决定向敌军投掷核弹。你被命令确定需要使用的弹头的威力。

敌人有 N 个具有重要战略意义的物体。他们的立场因情报部门而为人所知。打击的目的是使敌人至少 K 个重要目标失效。轰炸落点已确定,坐标为[X0; Y0]。

核弹头以估计撞击半径R≥0为标志。距轰炸震中距离R较近的所有建筑物都将被摧毁。所有距离震中 R 更远的建筑物也可以以一定的概率被停用。假设 D 是建筑物与震中之间的距离。该建筑物的失活概率P(D,R)根据以下公式计算:

$$P(D,R) = \begin{案例}
1 & ; \; D \leq R \\
\exp \left( 1 - \frac{D^2}{R^2} \right) & ; \; D > R
\end{案例}$$

如果弹头的预计撞击半径为零,那么位于撞击点的所有建筑物将被完全拆除,其余所有重要物体都不会受到损坏。

指挥官希望任务失败的概率不超过 ε。核弹头是一种太昂贵的奢侈品,这就是为什么你必须最小化弹头的估计影响半径。

输入

第一行包含一个整数N,代表敌人的物体数量(1 ≤ N ≤ 100)。第二行包含两个整数:K 是所需的停用对象数量,ε 是未完成任务的最大允许概率,以每密耳为单位(1 ≤ K ≤ N,1 ≤ ε ≤ 999)。第三行包含X0和Y0,它们是打击冲击点的坐标。接下来的 N 行包含两个数字 Xi 和 Yi,每个数字是每个具有战略意义的重要物体的坐标。所有坐标均为整数,其绝对值不超过1000。

让我们提醒您,每密耳有一千个单位(第一)。

一个点中可以有多个对象。

输出

打印所寻求的弹头的估计撞击半径。答案不准确度的绝对或相对度量不应超过 10 - 6。

示例

输入 #1

1
1 500
5 5
1 2

输出 #1

3.84257761518762740

输入 #2

5
3 100
0 0
3 4
60 70
100 100
10 10
5 12

输出 #2

13.45126176453737600