小小小朋友的小小世界

题目描述

给定一些点，求最小的可以把所有点都覆盖个的圆的半径

思路

什么乱七八糟的计算几何解析几何？都不会……

但我们发现了一些有意思的事情……

• 精确到小数点后6位
• 最多只有50个点
• 坐标最大1000

于是我们想到枚举圆心坐标

当然这明显是不行的

所以我们来用模拟退火

这题退火可跑的飞快，因为只有50个点，枚举一遍非常快

解释见注释

代码

#include<bits/stdc++.h>
#define double long double//强行提高精度
using namespace std;
struct node{
    double x,y;
}a[105];
int n;
double ansx,ansy,sy=0,sx=0;
double ans=2000,t;
double del=0.9995; //这个系数不算低，但是稳
inline double dis(node aa,node bb){
    return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y));
}//求欧几里得距离，用来看这个点里目前的圆心多远
double calc(double x,double y){
    double ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dis((node){x,y},a[i]));
    }
    return ans;
}//计算出若圆心在此处需多大半径
void SA(){//模拟退火
    double x=ansx,y=ansy;
    t=2000;//初温2000
    while(t>1e-14){//精细的降温
        double X=x+((rand()<<1)-RAND_MAX)*t;//随机得到一个x
        double Y=y+((rand()<<1)-RAND_MAX)*t;//随机得到一个y
        double now=calc(X,Y);
        double Delta=now-ans;//查看差值
        if(Delta<0){//接受这个新解
            x=X,y=Y;
            ans=now;
        }
        else if (exp(-Delta/t)*RAND_MAX>rand()) x=X,y=Y;
        //以一定概率接受这个新解
        t*=del;
    }
}
int main(){
    int cnt=0;
    srand(1000211237);//设置种子
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        sx+=a[i].x,sy+=a[i].y;
    }
    ansx=(double)sx/n,ansy=(double)sy/n;
    while((double)clock()/CLOCKS_PER_SEC<0.93) SA(),cnt++;
        //压线多次退火
    printf("%.14Lf",ans);//输出最后答案
    return 0;
}