#P3564. [SHOI2014]信号增幅仪

    ID: 2666 传统题 1000ms 256MiB 尝试: 836 已通过: 249 难度: 6 上传者: 标签>难度分类提高模拟与实现技巧坐标变换计算几何最小覆盖圆随机化与近似随机增量算法平方距离比较CF2100

[SHOI2014]信号增幅仪

[SHOI2014] 信号增幅仪

题目描述

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

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

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

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

输入格式

第一行一个整数 nn,表示用户数。接下来 nn 行每行两个整数 x,yx,y,表示一名用户的位置。

第 n+2n+2 行一个整数 aa,表示增幅方向,即从 xx 轴正方向逆时针旋转 aa 度。第 n+3n+3 行一个整数 pp,表示沿该方向放大的倍数。

输出格式

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

样例 #1

2
1 0
-1 0
0
2
0.500

样例 #2

3
1 1
-1 -1
0 0
45
7
0.202

数据范围

  • 对于 10%10\% 的数据,保证最优方案的中心在原点。
  • 对于 20%20\% 的数据,保证点是随机生成的。
  • 对于 30%30\% 的数据,n≤100n\le100。
  • 对于 50%50\% 的数据,n≤5000n\le5000。
  • 对于 100%100\% 的数据,n≤50000n\le50000,0≤a<1800\le a<180,1≤p≤1001\le p\le100,∣x∣,∣y∣≤2×108|x|,|y|\le2\times10^8。