U117348.Light It Up
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
在 xy 平面上有 N 个人,第 i 个人的坐标为 (Xi,Yi)。
其中有 K 个人身上带了灯,这些人的编号分别是 A1,A2,…,AK。
当一个带灯的人开启强度为 R 的灯时,以他为圆心、半径为 R 的圆内(包括边界)的所有人都会被照亮。
现在要求所有的 N 个人都至少被一盏灯照亮,且所有灯的强度 R 必须相同。
请你求出满足条件的最小灯光强度 R。只要你的答案与标准答案的误差不超过 10−5 即视为正确。
输入格式
第一行包含两个整数 N 和 K。
第二行包含 K 个整数 A1,A2,…,AK,表示带灯人的编号。
接下来的 N 行,第 i 行包含两个整数 Xi 和 Yi,表示第 i 个人的坐标。
输出格式
输出一个实数,表示所需的最小强度 R。
输入输出样例
输入#1
4 2 2 3 0 0 0 1 1 2 2 0
输出#1
2.2360679775
输入#2
2 1 2 -100000 -100000 100000 100000
输出#2
282842.7124746190
说明/提示
【样例 1 解释】
第 2 人和第 3 人有灯。
- 第 1 人到最近的灯(第 2 人)距离为 (0−0)2+(0−1)2=1。
- 第 4 人到最近的灯(第 3 人)距离为 (2−1)2+(0−2)2=5≈2.236。
要让所有人被照亮,R 至少要能覆盖到离灯最远的那个人,所以 R=5。
【数据范围】
- 1≤K<N≤1000
- 1≤Ai≤N
- −105≤Xi,Yi≤105
输入解题思路,AI测评打分。不知道怎么写?