题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3564
题意:给出平面上n个点,画出一个椭圆,椭圆的长轴是短轴的p倍,且长轴的方向为x轴逆时针旋转a度。求这个椭圆短轴的最小值使得可以覆盖所以点。
思路:先将所有点顺时针旋转a,然后所有点的x缩为原来的1/p。然后就是最小圆覆盖。
const int N=50005; struct point { double x,y; point(double _x=0,double _y=0) { x=_x; y=_y; } point operator-(point a) { return point(x-a.x,y-a.y); } point operator+(point a) { return point(x+a.x,y+a.y); } double operator*(point a) { return x*a.y-y*a.x; } point operator*(double t) { return point(x*t,y*t); } point operator/(double t) { return point(x/t,y/t); } point zhuan(double ang) { return point(x*cos(ang)+y*sin(ang),x*sin(ang)-y*cos(ang)); } point verl() { return point(-y,x); } }; point p[N]; int n; double dis(point a,point b) { return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); } int sgn(double x) { if(x>1e-20) return 1; if(x<-1e-20) return -1; return 0; } point cross(point a,point b,point p,point q) { double s1=(q-a)*(p-a); double s2=(p-b)*(q-b); return (a*s2+b*s1)/(s1+s2); } point get(point a,point b,point c) { double x=(b-a)*(c-a); if(sgn(x)==0) { double ab=dis(a,b); double bc=dis(b,c); double ac=dis(a,c); if(sgn(ab-bc)>=0&&sgn(ab-ac)>=0) return (a+b)/2; if(sgn(bc-ab)>=0&&sgn(bc-ac)>=0) return (b+c)/2; return (a+c)/2; } point M1=(a+b)/2,v1=(a-b).verl(); point M2=(b+c)/2,v2=(b-c).verl(); return cross(M1,M1+v1,M2,M2+v2); } int main() { scanf("%d",&n); int i; for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); double ang,scal; scanf("%lf%lf",&ang,&scal); ang=ang/180*PI; for(i=0;i<n;i++) { p[i]=p[i].zhuan(ang); p[i].x/=scal; } double r=0; point c=p[0]; for(i=1;i<n;i++) if(dis(p[i],c)>r+1e-10) { c=p[i]; r=0; int j; for(j=0;j<i;j++) if(dis(p[j],c)>r+1e-10) { c=(p[i]+p[j])/2; r=dis(p[i],p[j])/2; int k; for(k=0;k<j;k++) if(dis(p[k],c)>r+1e-10) { c=get(p[i],p[j],p[k]); r=max(dis(p[i],c),max(dis(p[k],c),dis(p[j],c))); } } } printf("%.3lf\n",r); }