帮助 ... 工作原理 键盘 define ems 数据 blog ref
3564: [SHOI2014] 信号增幅仪
Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 738 Solved: 290
[ Submit ][ Status ][ Discuss ]
Description
无线网络基站在理想状况下有效信号覆盖范围是个圆形.而无线基站的功耗与圆的半径的平方成正比.现给出平面
上若干网络用户的位置, 请你选择一个合适的位置建设无线基站.... 就在你拿起键盘准备开始敲代码的时候, 你的好
朋友发明家 SHTSC 突然出现了.SHTSC 刚刚完成了他的新发明--无线信号增幅仪.增幅仪能够在不增加无线基
站功耗的前提下, 使得有效信号的覆盖范围在某一特定方向上伸长若干倍.即: 使用了增幅仪的无线基站覆盖范围是
个椭圆, 其功耗正比于半短轴长的平方.现给出平面上若干网络用户的位置, 请你选择一个合适的位置建设无线基站
, 并在增幅仪的帮助下使所有的用户都能接收到信号, 且无线基站的功耗最小.注意: 由于 SHTSC 增幅仪的工作原理
依赖地磁场, 增幅的方向是恒定的.
Input
第一行一个整数: n.平面内的用户个数.之后的 n 行每行两个整数 x, y, 表示一个用户的位置.第 n+2 行一个整
数: a.表示增幅仪的增幅方向, 单位是度.表示增幅仪的方向是从 x 正方向逆时针转 a 度.第 n+3 行一个整数: p
.表示增幅仪的放大倍数.
Output
输出一行一个实数, 为能够覆盖所有用户的最小椭圆的半短轴长, 四舍五入到三位小数.
Sample Input
样例一:
2
1 0
-1 0
0
2
Sample Output
样例一:
0.500
HINT
对于 100% 的数据, n≤50000,0≤a<180,1≤p≤100,|x|,|y|≤2×10^8.
Source
By 佚名提供
坐标系直到 x 轴与椭圆长轴平行
点的坐标变换用旋转公式就可以了
因为是椭圆,所以所有点横坐标 除上 p
然后最小圆覆盖
#include<bits/stdc++.h>
#define N 50005
using namespace std;
int n,deg,p;double r;
const double pi=acos(-1);
struct P{
double x,y;
P operator - (const P &b)const{return (P){x-b.x,y-b.y};}
}a[N],c;
P rotate(P t,int tmp){
double rt=1.0*tmp/180*pi;P ret;
ret.x=t.x*cos(rt)-t.y*sin(rt);
ret.y=t.x*sin(rt)+t.y*cos(rt);
return ret;
}
double len(P a){return sqrt(a.x*a.x+a.y*a.y);}
P getcentre(P A,P B,P C){
double a1=B.x-A.x,b1=B.y-A.y,c1=(a1*a1+b1*b1)/2;
double a2=C.x-A.x,b2=C.y-A.y,c2=(a2*a2+b2*b2)/2;
double d=a1*b2-b1*a2;P ret;
ret.x=A.x+(c1*b2-c2*b1)/d;
ret.y=A.y+(c2*a1-c1*a2)/d;
return ret;
}
void getcircle(){
random_shuffle(a+1,a+1+n);
c=a[1];r=0;
for(int i=1;i<=n;i++){
if(len(a[i]-c)<=r)continue;
c=a[i];r=0;
for(int j=1;j<i;j++){
if(len(a[j]-c)<=r)continue;
c.x=(a[i].x+a[j].x)/2;
c.y=(a[i].y+a[j].y)/2;
r=len(a[j]-c);
for(int k=1;k<j;k++){
if(len(a[k]-c)<=r)continue;
c=getcentre(a[i],a[j],a[k]);
r=len(a[i]-c);
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
scanf("%d%d",°,&p);
for(int i=1;i<=n;i++)
a[i]=rotate(a[i],-deg),a[i].x/=p;
getcircle();printf("%.3lf\n",r);
return 0;
}
bzoj3564[SHOI2014] 信号增幅仪
来源: http://www.bubuko.com/infodetail-2469733.html