思路:
首先我们将所有的点都顺时针旋转\(a\)度,这样就相当于坐标系逆时针旋转了\(a\)度,那么现在椭圆的长轴就与\(x\)轴平行了.
那么还要考虑椭圆现在是横向伸长了\(p\)倍,于是我们就将所有点目前的横坐标缩小\(p\)倍.
然后就是随机增量法的最小圆覆盖了.
#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> #include<cmath> using namespace std; typedef double f2; static const f2 eps=1e-7; inline int dcmp(const f2&x){return fabs(x)<eps?0:(x<0?-1:1);} #define N 50010 struct Point{ f2 x,y; Point(){} Point(f2 _x,f2 _y):x(_x),y(_y){} inline void read(){scanf("%lf%lf",&x,&y);} bool operator<(const Point&B)const{return dcmp(x-B.x)==0?y<B.y:x<B.x;} Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);} Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);} Point operator*(const f2&p)const{return Point(p*x,p*y);} Point operator/(const f2&p)const{return Point(x/p,y/p);} }P[N]; f2 getdis(const Point&a,const Point&b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} f2 cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;} Point getmid(const Point&a,const Point&b){return Point((a.x+b.x)/2,(a.y+b.y)/2);} Point getvec(const Point&v){return Point(-v.y,v.x);} Point rot(const Point&p,f2 alp){return Point(p.x*cos(alp)-p.y*sin(alp),p.x*sin(alp)+p.y*cos(alp));} struct Line{ Point p,v; Line(){} Line(const Point&p1,const Point&p2):p(p1),v(p1-p2){} }; Line getvecline(const Point&p1,const Point&p2){ Line re; re.p=getmid(p1,p2),re.v=getvec(p1-p2); return re; } Point getlineintersection(const Line&l1,const Line&l2){ return l1.p+l1.v*(cross(l1.p-l2.p,l2.v)/cross(l1.v,l2.v)); } Point getpoint(Point p1,Point p2,Point p3){ static Point P[3];P[0]=p1,P[1]=p2,P[2]=p3;sort(P,P+3);p1=P[0],p2=P[1],p3=P[2]; if(dcmp(cross(p1-p2,p2-p3))==0)return getmid(p1,p3); else return getlineintersection(getvecline(p1,p2),getvecline(p2,p3)); } int main(){ int n;scanf("%d",&n);register int i,j,k; for(i=1;i<=n;++i)P[i].read(); f2 alp,p;scanf("%lf%lf",&alp,&p); for(i=1;i<=n;++i)P[i]=rot(P[i],-alp/180*acos(-1.0)),P[i].x/=p; for(i=2;i<=n;++i)swap(P[i],P[rand()%i+1]); Point o=P[1];f2 r=0; for(i=2;i<=n;++i)if(getdis(o,P[i])>r){ o=P[i],r=0; for(j=1;j<i;++j)if(getdis(o,P[j])>r){ o=getmid(P[i],P[j]),r=getdis(o,P[i]); for(k=1;k<j;++k)if(getdis(o,P[k])>r)o=getpoint(P[i],P[j],P[k]),r=getdis(o,P[i]); } } printf("%.3lf",r); return 0; }