U117348.Light It Up

普及-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

xyxy 平面上有 NN 个人,第 ii 个人的坐标为 (Xi,Yi)(X_i, Y_i)
其中有 KK 个人身上带了灯,这些人的编号分别是 A1,A2,,AKA_1, A_2, \dots, A_K

当一个带灯的人开启强度为 RR 的灯时,以他为圆心、半径为 RR 的圆内(包括边界)的所有人都会被照亮。
现在要求所有的 NN 个人都至少被一盏灯照亮,且所有灯的强度 RR 必须相同。

请你求出满足条件的最小灯光强度 RR。只要你的答案与标准答案的误差不超过 10510^{-5} 即视为正确。

输入格式

第一行包含两个整数 NNKK
第二行包含 KK 个整数 A1,A2,,AKA_1, A_2, \dots, A_K,表示带灯人的编号。
接下来的 NN 行,第 ii 行包含两个整数 XiX_iYiY_i,表示第 ii 个人的坐标。

输出格式

输出一个实数,表示所需的最小强度 RR

输入输出样例

  • 输入#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 人)距离为 (00)2+(01)2=1\sqrt{(0-0)^2+(0-1)^2} = 1
  • 第 4 人到最近的灯(第 3 人)距离为 (21)2+(02)2=52.236\sqrt{(2-1)^2+(0-2)^2} = \sqrt{5} \approx 2.236
    要让所有人被照亮,RR 至少要能覆盖到离灯最远的那个人,所以 R=5R = \sqrt{5}

【数据范围】

  • 1K<N10001 \le K < N \le 1000
  • 1AiN1 \le A_i \le N
  • 105Xi,Yi105-10^5 \le X_i, Y_i \le 10^5

输入解题思路,AI测评打分。不知道怎么写?

首页