AT5294 [ABC151F] Enclose All

题目描述

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

思路

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

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

  • 精确到小数点后6位

  • 最多只有50个点

  • 坐标最大1000

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

当然这明显是不行的

所以我们来用模拟退火

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

解释见注释

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;
}