Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

03/23
20:31
计算几何基础 随机化

[bzoj 2823] AHOI2012 信号塔

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

共N+1行,第一行为正整数N(1≤N≤1000000),表示队员个数。接下来

N行,每行两个实数用空格分开,分别是第i个队员的坐标X

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一行,共三个实数(中间用空格隔开),分别是信号塔的坐标,和信号塔 覆盖的半径。 (注:队员是否在边界上的判断应符合他到圆心的距离与信号塔接收半径之差的绝对值小于10^-6

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

5
1.200 1.200
2.400 2.400
3.800 4.500
2.500 3.100
3.900 1.300

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2.50 2.85 2.10

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

1≤N≤500000

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

随机增量法求最小覆盖圆啊= 网上的内些模拟退火凸包暴力的都是什么鬼 反正本蒟蒻不会QAQ

c++:

pascal:

 

[bzoj 2823] AHOI2012 信号塔