问题 22216 --NOI2014湖北省选一试第1题 信号增幅仪

22216: NOI2014湖北省选一试第1题 信号增幅仪

时间限制: 1 Sec  内存限制: 256 MB
提交: 34  解决: 5
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][98432kb]

题目描述

无线网络基站在理想状况下有效信号覆盖范围是个圆形。而无线基站的功耗与圆的半径的平方成正比。现给出平面上若干网络用户的位置,请你选择一个合适的位置建设无线基站 ……

就在你拿起键盘准备开始敲代码的时候,你的好朋友发明家SHTSC突然出现了。SHTSC刚刚完成了他的新发明——无线信号增幅仪。增幅仪能够在不增加无线基站功耗的前提下,使得有效信号的覆盖范围在某一特定方向上伸长若干倍。即:使用了增幅仪的无线基站覆盖范围是个椭圆,其功耗正比于半短轴长的平方。

现给出平面上若干网络用户的位置,请你选择一个合适的位置建设无线基站,并在增幅仪的帮助下使所有的用户都能接收到信号,且无线基站的功耗最小。

注意:由于SHTSC增幅仪的工作原理依赖地磁场,增幅的方向是恒定的。

输入

第一行一个整数:n。平面内的用户个数。

之后的n行每行两个整数x, y,表示一个用户的位置。

n+2行一个整数:a。表示增幅仪的增幅方向,单位是度。表示增幅仪的方向是从x正方向逆时针转a度。

n+3行一个整数:p。表示增幅仪的放大倍数。


【数据规模】

对于10%的数据,保证最优方案的心在原点。

对于20%的数据,保证点是随机生成的。

对于30%的数据,n≤100

对于50%的数据,n≤5000

对于100%的数据,n≤500000≤a<1801≤p≤100|x|,|y|≤2×108


输出

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


amplifier1.in

amplifier1.out

2

1 0

-1 0

0

2

 

0.500

 

amplifier2.in

amplifier2.out

3

1 1

-1 -1

0 0

45

7

 

0.202


样例输入

2
1 0
-1 0
0
2

样例输出

0.500

提示

来源

[提交][状态]