#P2533. [AHOI2012] 信号塔

    ID: 1547 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>计算几何2012各省省选安徽随机贪心,随机化

[AHOI2012] 信号塔

题目描述

在野外训练中,为了确保每位参加集训的成员安全,实时的掌握和收集周边环境和队员信息非常重要,集训队采用的方式是在训练所在地散布 NN 个小型传感器来收集并传递信息,这些传感器只与设在集训地中的信号塔进行通信,信号塔接收信号的覆盖范围是圆形,可以接收到所有分布在该集训区域内所有 NN 个小型传感器(包括在该圆形的边上)发出的信号。信号塔的功率与信号塔接收范围半径的大小成正比,因为是野外训练,只能使用事先储备好的蓄电设备,因此在可以收集所有传感器信息的基础上,还应使得信号塔的功率最小。小龙帮助教官确定了一种信号塔设置的方案,既可以收集到所有 NN 个传感器的信号,又可以保证这个信号塔的功率是最小的。同学们,你们知道,这个信号塔的信号收集半径有多大,它应该设置在何处吗?

输入格式

N+1N+1 行,第一行为正整数 NN,表示队员个数。接下来 NN 行,每行两个实数用空格分开,分别是第 ii 个队员的坐标 xix_iyiy_ixi,yix_i,y_i 不超过双精度范围)。

输出格式

一行,共三个实数(中间用空格隔开),分别是信号塔的坐标,和信号塔覆盖的半径。

5
1.200 1.200
2.400 2.400
3.800 4.500
2.500 3.100
3.900 1.300
2.50 2.85 2.10

提示

队员是否在边界上的判断应该符合他到圆心的距离与信号塔接受半径的差的绝对值小于 10610^{-6},最终结果保留 22 位小数。

对于 30%30\% 的数据,满足 1N1041\le N \le 10^4
对于 70%70\% 的数据,满足 1N2×1041\le N \le 2\times10^4
对于 100%100\% 的数据,满足 1N1061\le N \le 10^6

本题存在 hack 数据,计 0 分。