hdu 3932 Groundhog Build Home —— 模拟退火

时间:2023-12-22 12:16:56

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3932

找一个位置使距离最远的点的距离最小;

上模拟退火;

每次向距离最远的点移动,注意判断一下距离最远的点距离为0的情况。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<ctime>
#define eps 1e-15
#define dc 0.99
using namespace std;
typedef double db;
int const xn=;
int n,xx[xn],yy[xn],rx,ry;
db ansx,ansy,ans;
db dist(db x,db y,db a,db b){return sqrt((x-a)*(x-a)+(y-b)*(y-b));}
void SA()
{
db T=,x=ansx/n,y=ansy/n,tx,ty; int id;
ans=1e9;
while(T>eps)
{
db ret=-,k;
for(int i=;i<=n;i++)
if(ret<(k=dist(x,y,xx[i],yy[i])))id=i,ret=k;
if(ret!=-&&ret<ans)ans=ret,ansx=x,ansy=y;
x+=(xx[id]-x)/ret*T;
y+=(yy[id]-y)/ret*T;
T*=dc;
}
}
int main()
{
srand(time());
while(~scanf("%d%d%d",&rx,&ry,&n))
{
ansx=; ansy=;
for(int i=;i<=n;i++)
scanf("%d%d",&xx[i],&yy[i]),ansx+=xx[i],ansy+=yy[i];
SA();
printf("(%.1lf,%.1lf).\n%.1lf\n",ansx,ansy,ans);
}
return ;
}