Light It Up

题目描述

在 $xy$ 平面上有 $N$ 个人，编号为 $1,2,\dots,N$。第 $i$ 个人位于坐标 $(X_i, Y_i)$。
其中 $K$ 个人，编号为 $A_1, A_2, \dots, A_K$，将获得相同强度的灯光。
当位于 $(x,y)$ 的人拥有强度为 $R$ 的灯时，该灯会照亮以 $(x,y)$ 为中心、半径为 $R$ 的圆的内部（包括边界）。
求使得每个人至少被一盏灯照亮所需的最小灯光强度。

输入格式

输入按下述格式从标准输入给出： $N$ $K$ $A_1$ $A_2$ $\dots$ $A_K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

输出格式

输出一个实数作为答案。
只要你的输出与评测输出的绝对或相对误差不超过 $10^{-5}$，就会被判为正确。

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

2.23606797749978969

2 1
2
-100000 -100000
100000 100000

282842.712474619009

8 3
2 6 8
-17683 17993
93038 47074
58079 -57520
-41515 -89802
-72739 68805
24324 -73073
71049 72103
47863 19268

130379.280458974768

提示

输入中的所有数值均为整数。 1 \le K < N \le 1000 1 \le A_1 < A_2 < \dots < A_K \le N $|X_i|,|Y_i| \le 10^5$ 若 $i \neq j$，则 $(X_i,Y_i) \neq (X_j,Y_j)$。此样例输入包含四个人。其中第 $2$ 和第 $3$ 个人将拥有灯光。
当 $R \ge \sqrt{5} \approx 2.236068$ 时，每个人至少会被一盏灯照亮。

标签: AtCoder|abc255B

来源

AtCoder|abc255B