思路:

首先我们将所有的点都顺时针旋转\(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;
}

思路:

本来想写的是求出凸包然后在凸包上\(O(n^3)\)进行暴力的算法.虽然平面上的随机点形成的凸包点数很少,不过显然如果直接给出一个凸包就直接卡掉了.

于是我学习的是随机增量法求最小圆覆盖.

网上题解很多,就不解释了(还不太懂),如果随机打乱一下的话,好像是能够做到期望\(O(n)\),相当厉害的算法.

一个麻烦就是求出三角形的外心,用了一大堆叉积来算好像很傻逼...

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 1010

#define eps 1e-8
typedef double f2;
struct Point{
    f2 x,y;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
    bool operator<(const Point&B)const{return 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){return Point(p*x,p*y);}
    Point operator/(const f2&p){return Point(x/p,y/p);}
}P[N];
inline f2 sqr(const f2&x){return x*x;}
f2 Cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;} 
f2 getdist(const Point&a,const Point&b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}

struct Line{
    Point p,v;
    Line(){}
    Line(Point _p,Point _v):p(_p),v(_v){}
};
Point GetLineIntersection(Line L1,Line L2){
    return L1.p+L1.v*(Cross(L1.p-L2.p,L2.v)/Cross(L1.v,L2.v));
}
Point Getvert(const Point&a){return Point(-a.y,a.x);}
Point Getmid(const Point&a,const Point&b){return Point((a.x+b.x)/2,(a.y+b.y)/2);}

Line GetLine(const Point&a,const Point&b){
    return Line(Getmid(a,b),Getvert(a-b));
}
Point Getcenter(Point a,Point b,Point c){
    Point P[3]={a,b,c};sort(P,P+3);a=P[0],b=P[1],c=P[2];
    if(fabs(Cross(a-b,b-c))<eps)return Getmid(a,c);
    else return GetLineIntersection(GetLine(a,b),GetLine(b,c));
}
    
int main(){
    int X,Y,n;register int i,j,k;
    while(scanf("%d%d%d",&X,&Y,&n)!=EOF){
        for(i=1;i<=n;++i)scanf("%lf%lf",&P[i].x,&P[i].y);
        random_shuffle(P+1,P+n+1);
        Point center=P[1];f2 r=0;
        for(i=2;i<=n;++i){
            if(getdist(center,P[i])>r){
                center=P[i],r=0;
                for(j=1;j<i;++j){
                    if(getdist(center,P[j])>r){
                        center=Getmid(P[i],P[j]),r=getdist(P[i],P[j])*.5;
                        for(k=1;k<j;++k)
                            if(getdist(center,P[k])>r)center=Getcenter(P[i],P[j],P[k]),r=getdist(center,P[i]);
                    }
                }
            }
        }
        printf("(%.1lf,%.1lf).\n%.1lf\n",center.x,center.y,r);
    }
    return 0;
}