Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 834 Solved: 337
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。
/**************************************************************
Problem: 3564
User: ictsing
Language: C++
Result: Accepted
Time:544 ms
Memory:2072 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const double pi=acos(-1.0);
const int mt=50000+5;
const double eps=1e-8;
double r;
struct point{
double x,y;//
}p[mt],o;
point rotat(point a,double angle,point b)
{
b.x-=a.x,b.y-=a.y;point tp;
tp.x=cos(angle)*b.x-sin(angle)*b.y+a.x;
tp.y=sin(angle)*b.x+cos(angle)*b.y+a.y;
return tp;
}
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
point circle(point A,point B,point C)
{
double a1=B.x-A.x,b1=B.y-A.y,c1=(a1*a1+b1*b1)/2.0;
double a2=C.x-A.x,b2=C.y-A.y,c2=(a2*a2+b2*b2)/2.0;
double d=a1*b2-a2*b1;
point ovo;
ovo.x=A.x+(c1*b2-c2*b1)/d;
ovo.y=A.y+(a1*c2-a2*c1)/d;
return ovo;
}
void mincovercircle(int n)
{
random_shuffle(p+1,p+n+1);
o=p[1],r=0;
for(int i=1;i<=n;i++)
{
if(dis(p[i],o)>eps+r)
{
o=p[i],r=0;
for(int j=1;j<i;j++)
if(dis(p[j],o)>eps+r)
{
o.x=(p[i].x+p[j].x)/2;
o.y=(p[i].y+p[j].y)/2;
r=dis(p[j],o);
for(int k=1;k<j;k++)
if(dis(p[k],o)>eps+r)
{
o=circle(p[i],p[j],p[k]);
r=dis(p[k],o);
}
}
}
}
}
int main()
{
int n=read();
p[0].x=0,p[0].y=0;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
double a,qaq; scanf("%lf%lf",&a,&qaq);
double angel=-a/180*pi;
for(int i=1;i<=n;i++)
p[i]=rotat(p[0],angel,p[i]),p[i].x/=qaq;
mincovercircle(n);
int tat;
//qaq=(int)r*10000,tat=qaq/10;qaq=qaq-tat*10;
//if(qaq>4) printf("%.3lf\n",r+0.001);
// else 说好的四舍五入，怎么四舍五入还错了呢
printf("%.3lf\n",r);
return 0;
}
/*
2
1 0
-1 0
0
2
0.500
*/
/**************************************************************
Problem: 3564
User: ictsing
Language: C++
Result: Accepted
Time:544 ms
Memory:2072 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const double pi=acos(-1.0);
const int mt=50000+5;
const double eps=1e-8;
double r;
struct point{
double x,y;//
}p[mt],o;
point rotat(point a,double angle,point b)
{
b.x-=a.x,b.y-=a.y;point tp;
tp.x=cos(angle)*b.x-sin(angle)*b.y+a.x;
tp.y=sin(angle)*b.x+cos(angle)*b.y+a.y;
return tp;
}
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
point circle(point A,point B,point C)
{
double a1=B.x-A.x,b1=B.y-A.y,c1=(a1*a1+b1*b1)/2.0;
double a2=C.x-A.x,b2=C.y-A.y,c2=(a2*a2+b2*b2)/2.0;
double d=a1*b2-a2*b1;
point ovo;
ovo.x=A.x+(c1*b2-c2*b1)/d;
ovo.y=A.y+(a1*c2-a2*c1)/d;
return ovo;
}
void mincovercircle(int n)
{
random_shuffle(p+1,p+n+1);
o=p[1],r=0;
for(int i=1;i<=n;i++)
{
if(dis(p[i],o)>eps+r)
{
o=p[i],r=0;
for(int j=1;j<i;j++)
if(dis(p[j],o)>eps+r)
{
o.x=(p[i].x+p[j].x)/2;
o.y=(p[i].y+p[j].y)/2;
r=dis(p[j],o);
for(int k=1;k<j;k++)
if(dis(p[k],o)>eps+r)
{
o=circle(p[i],p[j],p[k]);
r=dis(p[k],o);
}
}
}
}
}
int main()
{
int n=read();
p[0].x=0,p[0].y=0;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
double a,qaq; scanf("%lf%lf",&a,&qaq);
double angel=-a/180*pi;
for(int i=1;i<=n;i++)
p[i]=rotat(p[0],angel,p[i]),p[i].x/=qaq;
mincovercircle(n);
int tat;
//qaq=(int)r*10000,tat=qaq/10;qaq=qaq-tat*10;
//if(qaq>4) printf("%.3lf\n",r+0.001);
// else 说好的四舍五入，怎么四舍五入还错了呢
printf("%.3lf\n",r);
return 0;
}
/*
2
1 0
-1 0
0
2
0.500
*/
评论