4215: 「SHOI2014」信号增幅仪

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

无线网络基站在理想状况下有效信号覆盖范围是个圆形。而无线基站的功耗与圆的半径的平方成正比。 现给出平面上若干网络用户的位置,请你选择一个合适的位置建设无线基站……就在你拿起键盘准备开始敲代码的时候,你的好朋友发明家 SHTSC 突然出现了。SHTSC 刚刚完成了他的新发明——无线信号增幅仪。增幅仪能够在不增加无线基站功耗的前提下,使得有效信号的覆盖范围在某一特定方向上伸长若干倍。即:使用了增幅仪的无线基站覆盖范围是个椭圆,其功耗正比于半短轴长的平方。 现给出平面上若干网络用户的位置,请你选择一个合适的位置建设无线基站,并在增幅仪的帮助下使所有的用户都能接收到信号,且无线基站的功耗最小。 **注意**:由于 SHTSC 增幅仪的工作原理依赖地磁场,增幅的方向是恒定的。

输入

第一行一个整数 $n$,平面内的用户个数。 之后的 $n$ 行每行两个整数 $x, y$,表示一个用户的位置。 第 $n+2$ 行一个整数 $a$,表示增幅仪的增幅方向,单位是度,表示增幅仪的方向是从 $x$ 正方向逆时针转 $a$ 度。 第 $n+3$ 行一个整数 $p$,表示增幅仪的放大倍数。

输出

输出一行一个实数,为能够覆盖所有用户的最小椭圆的半短轴长,四舍五入到三位小数。

样例输入 复制

2
1 0
-1 0
0
2

样例输出 复制

0.500

提示


数据范围:对于 $100\%$ 的数据,$n \leq 50000,\ 0 \leq a<180,\ 1\leq p \leq 100,\ |x|,|y|\leq 2 \times 10^8$。

来源/分类