最小覆盖圆求助
  • 板块题目总版
  • 楼主leiwusi
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/18 23:05
  • 上次更新2024/3/19 13:44:54
查看原帖
最小覆盖圆求助
525038
leiwusi楼主2024/3/18 23:05

rt

#include<iostream>
#include<algorithm>
#include<random>
#include<cmath>
using namespace std;
typedef double dd;
const int MAXN = 1e5+114;

struct point{dd x,y;} O,a[MAXN],b[MAXN];//a为原始数组,b为使用数组
dd r,eps = 1e-10;
int n;
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*ff;
}
void write(int x){
    if(x<0){x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}
void writeln(int x){write(x),puts("");}

double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void twcir(point a,point b){
    O = (point){(a.x+b.x)/2,(a.y+b.y)/2};
    r = dis(O,a);
}

void thcir(point A,point B,point C){
    double aa,bb,cc,dd,ee,ff;
    aa=A.x-C.x;bb=A.y-C.y;
    cc=B.x-C.x;dd=B.y-C.y;
    ee=A.x*A.x+A.y*A.y-C.x*C.x-C.y*C.y;
    ff=B.x*B.x+B.y*B.y-C.x*C.x-C.y*C.y;
    O.x=(dd*ee-bb*ff)/(2*aa*dd-2*bb*cc);
    O.y=(aa*ff-cc*ee)/(2*aa*dd-2*bb*cc);
    r=dis(O,A);
    //printf("%.5lf %.5lf\n",O.x,O.y);
    //printf("%.5lf %.5lf %.5lf\n",dis(O,A),dis(O,B),dis(O,C));
}

void get_cir(int l,int r){
    int tot=0;
    for(int i=l;i<=r;i++) b[++tot]=a[i];
    for(int i=1;i<=tot;i++) swap(b[i],b[rand()%tot+1]);
    
    r = 0;O = b[1];
    for(int i = 2;i<=tot;i++){
        if(dis(O,b[i])>r+eps){
            O = b[i];r = 0;
            for(int j = 1;j<i;j++){
                if(dis(O,b[j])>r+eps){
                    twcir(b[i],b[j]);
                    for(int k = 1;k<j;k++){
                        if(dis(O,b[k])>r+eps){
                            thcir(b[i],b[j],b[k]);
                        }
                    }
                }
            }
        }
    }
}

int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    get_cir(1,n);
    cout<<r<<endl;
    cout<<O.x<<" "<<O.y<<endl;
    return 0;

}






2024/3/18 23:05
加载中...