#P3564. [SHOI2014]信号增幅仪
[SHOI2014]信号增幅仪
[SHOI2014] 信号增幅仪
题目描述
无线网络基站在理想状况下有效信号覆盖范围是个圆形。而无线基站的功 耗与圆的半径的平方成正比。现给出平面上若干网络用户的位置,请你选择一 个合适的位置建设无线基站 ……
就在你拿起键盘准备开始敲代码的时候,你的好朋友发明家SHTSC 突然出 现了。SHTSC 刚刚完成了他的新发明——无线信号增幅仪。增幅仪能够在不增 加无线基站功耗的前提下,使得有效信号的覆盖范围沿某个固定方向放大。椭圆的半长轴为半短轴的 倍。即:使用了增幅仪的无线基站覆盖范围是个椭圆,其功耗正比于半短轴 长的平方。
现给出平面上若干网络用户的位置,请你选择一个合适的位置建设无线基 站,并在增幅仪的帮助下使所有的用户都能接收到信号,且无线基站的功耗最 小。
注意:由于SHTSC 增幅仪的工作原理依赖地磁场,增幅的方向是恒定的。
输入格式
第一行一个整数 ,表示用户数。接下来 行每行两个整数 ,表示一名用户的位置。
第 行一个整数 ,表示增幅方向,即从 轴正方向逆时针旋转 度。第 行一个整数 ,表示沿该方向放大的倍数。
输出格式
输出一行一个实数,为能够覆盖所有用户的最小椭圆的半短轴长,四舍五入到三位小数。
样例 #1
2
1 0
-1 0
0
2
0.500
样例 #2
3
1 1
-1 -1
0 0
45
7
0.202
数据范围
- 对于 的数据,保证最优方案的中心在原点。
- 对于 的数据,保证点是随机生成的。
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,,,,。