发布时间：2024-07-31

最小圆覆盖

struct Circle{
    Point p;
    double r;
};

pair<Point,Point> get_line(Point a,Point b){
    //找到与向量ab垂直的向量的起点与终点
    return {(a+b)/2,rotate(b-a,PI/2)};
}

Circle get_circle(Point a,Point b,Point c){
    //根据不共线的三点求出圆的圆心坐标和半径
    auto u=get_line(a,b),v=get_line(a,c);//求出垂直于ab和ac的向量
    auto get_line_intersection=[&](Point p,Vector v,Point q,Vector w){
        Vector u=p-q;
        double t=cross(w,u)/cross(v,w);
        return p+v*t;
    };
    auto p=get_line_intersection(u.first,u.second,v.first,v.second);//两向量交点即为所求圆的圆心
    return {p,(p-a).length()};
}
//----------------求最小圆覆盖,期望O(n)---------------------
Circle smallest_circle(vector<Point> &po){
    random_shuffle(po.begin(),po.end());
    Circle c={po[0],0};//最开始时直接将第一个点看作圆心，半径为0
    for(int i=1;i<po.size();i++){
        if(cmp(c.r,(c.p-po[i]).length())<0){
            //如果第i个点不在前i-1个点的最小圆覆盖内，则进入下一重循环
            c={po[i],0};//将第i个点当作圆心，半径为0，重新确定圆
            for(int j=0;j<i;j++){
                if(cmp(c.r,(c.p-po[j]).length())<0){
                    c={(po[i]+po[j])/2,(po[i]-po[j]).length()/2};
                    for(int k=0;k<j;k++){
                        if(cmp(c.r,(c.p-po[k]).length())<0){//确定了最小圆覆盖上的三个点，直接求出圆
                            c=get_circle(po[i],po[j],po[k]);
                        }
                    }
                }
            }
        }
    }
    return c;
}