jzoj 3660. 【SHTSC2014】信号增幅仪

本文主要是介绍jzoj 3660. 【SHTSC2014】信号增幅仪，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

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

Input

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

Output

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

Sample Input

Sample Output

输出1：
0.500
输出2：
0.202

Data Constraint

对于10%的数据，保证最优方案的中心在原点。
对于20%的数据，保证点是随机生成的。
对于30%的数据，n≤100。
对于50%的数据，n≤5000。
对于100%的数据，n≤50000，0≤a<180，1≤p≤100，|x|,|y|≤2×10^8。

Sulotion

因为只有固定的方向才能增幅，而结果为椭圆，于是我们可以把它缩放为增幅前的圆，
所以先旋转a度（用三角函数要转弧度），然后每个点横坐标除以p，最后最小圆覆盖。
最小圆覆盖的方法：随机增量法 http://blog.csdn.net/commonc/article/details/52291822（非常详细且证明了时间复杂度期望为O（n））
及已知三点求外接圆的方法 http://blog.csdn.net/liyuanbhu/article/details/52891868

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;#define N 50050
#define DB double
#define pi 3.1415926535897932384626433832795struct note
{DB x,y;
};note a[N];
DB al,th,p,co,si,ans,s;
int n; DB sqr(DB x){return x*x;}
DB dis(note x,note y){return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));}
bool pd(int x) {return dis(a[0],a[x])<=s;} void init()
{scanf("%d",&n);int x,y;for (int i=1;i<=n;i++){scanf("%d%d",&x,&y);a[i].x=DB(x); a[i].y=DB(y);}scanf("%d%d",&x,&y);al=DB(x); p=DB(y);th=al*pi/180.00000;si=sin(th); co=cos(th);DB xx,yy;for (int i=1;i<=n;i++){xx=a[i].x; yy=a[i].y;a[i].x=si*yy+co*xx;a[i].y=co*yy-si*xx;a[i].x/=p;}
}note solve(note x,note y,note z)
{DB a,b,c,d,e,f;a=x.x-y.x; b=x.y-y.y; c=x.x-z.x; d=x.y-z.y;e=sqr(x.x)-sqr(y.x)+sqr(x.y)-sqr(y.y);  e/=2;f=sqr(x.x)-sqr(z.x)+sqr(x.y)-sqr(z.y);  f/=2;note re;re.x=-(d*e-b*f)/(b*c-a*d);re.y=-(a*f-c*e)/(b*c-a*d);return re;
}void find()
{random_shuffle(a+1,a+n+1);for (int i=1;i<=n;i++)if (pd(i)==false){a[0]=a[i]; s=0.0;for (int j=1;j<=i-1;j++)if (pd(j)==false){a[0].x=(a[i].x+a[j].x)/2; a[0].y=(a[i].y+a[j].y)/2;s=dis(a[i],a[j])/2;for (int k=1;k<=j-1;k++)if (pd(k)==false){a[0]=solve(a[i],a[j],a[k]);s=dis(a[0],a[i]);}}}
}int main()
{freopen("amplifier.in","r",stdin);freopen("amplifier.out","w",stdout);init();find();ans=s;printf("%.3lf\n",ans);return 0;
}