loj#P2548. 「JSOI2018」绝地反击

「JSOI2018」绝地反击

题目描述

由于你的出色表现,外星人的进攻已经被成功化解了。现在, JYY 召集了强大的黄金舰队,准备一击摧毁外星人的母舰。
黄金舰队共有 n(n3)n(n\ge 3) 艘飞船,这些飞船能将能量汇聚到同一点(外星人母舰所在位置),从而对外星母舰进行毁灭性的打击。 JYY 计划将所有飞船同时折跃到母舰附近,瞬间发动攻击结束战斗。
在黄金舰队折跃抵达后,由于各种不稳定因素,舰队中的各艘飞船并未进入最佳攻击位置,因此需要迅速对它们进行调整。现在,所有飞船已经同时完成了折跃,每个飞船都可以看做是平面上的一个点,第 i(1in)i(1\le i\le n) 艘飞船的坐标为 (xi,yi)(x_i,y_i) 。外星母舰位于坐标原点 (0,0)(0,0)
为了实现最高效的打击,所有飞船都必须移动到攻击轨道上。攻击轨道是圆心在原点 (0,0)(0,0) 、半径为 RR 的圆。因为发射产生的能量实在太大, JYY 希望发射时飞船相互之间的距离尽可能大。具体来说, JYY 希望黄金舰队所有 nn 艘飞船均匀地排列在攻击轨道上(所有飞船均为同一型号,因此按任意顺序排列均可),即相邻飞船在攻击轨道(圆弧)上的距离相等且恰好等于 2πRn\frac{2\pi R}{n} 。换言之, JYY 希望调整所有飞船的位置,使得所有飞船都位于攻击轨道上,且它们恰好位于正 nn 边形的 nn个顶点。
请你帮助 JYY 计算出打击开始的最短时间(即所有飞船移动到攻击轨道上并等距排列的最少时间)。飞船一单位时间可以在平面上移动一单位距离,且飞船的体积可以看成 00 。因此在你设计的方案中,飞船在某个时刻 “相遇” 是允许的。此外,初始时飞船的坐标也允许重合。

输入格式

输入第一行两个整数 n,Rn,R ,表示飞船的数量和攻击轨道的半径。
接下来 nn 行,每行两个整数 (xi,yi)(x_i,y_i) ,分别表示每一艘飞船的坐标。

输出格式

输出一行,表示所有飞船就位的最短时间(请保留足够的小数位数)。如果你的输出和参考答案差距不超过 10610^{-6} 则认为正确。

3 1
0 0
0 0
0 0
1.00000000
3 10
10 0
0 10
10 10
12.17522858

数据范围与提示

对于 20%20\% 的数据,有 n=3n=3
对于 50%50\% 的数据,有 n50n\le 50
对于 100%100\% 的数据,有 $3 \le n\le 200,0 \le\vert x_i\vert,\vert y_i\vert,R\le 100$ 。