13秒,跑,往死里跑
犹豫就会wa
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
double ansx,ansy;
double temx,temy;
double delat=0.997;
int tt;
double x[10001];
double y[10001];
int m;
double xx;
double t;
double temmx;
double temmy;
double ans;
double yy;
double cal(double xxx,double yyy){
double re=10000000000.0;
for(int i=1;i<=m;++i){
re=min(re,sqrt((xxx-x[i])*(xxx-x[i])+(yyy-y[i])*(yyy-y[i])));
}
return re;
}
double ansxx;
double ansyy;
void sa(){
t=100;
// cout<<"FFF";
temx=fmod(fabs(rand())+xx,xx);
temy=fmod(fabs(rand())+yy,yy);
double temans=cal(temx,temy);
ans=cal(ansx,ansy);
while(t>1e-10){
temmx=temx+((rand()<<1)-RAND_MAX)*t;
temmy=temy+((rand()<<1)-RAND_MAX)*t;
// cout<<temmx<<endl;
if(temmx<1e-5||temmy<1e-5||temmx>xx||temmy>yy){
t*=delat;
continue;
}
double now=cal(temmx,temmy);
double cha=temans-now;
if(cha<0){
temans=ans=now;
temx=ansx=temmx;
temy=ansy=temmy;
}else{
if(exp(-cha/t)*RAND_MAX>(double)rand()){
temx=temmx;
temy=temmy;
temans=now;
}
}
t*=delat;
}
}
int main(){
read(tt);
while(tt--){
cin>>xx>>yy>>m;
ansx=0;
ansy=0;
for(int i=1;i<=m;++i){
scanf("%lf%lf",&x[i],&y[i]);
ansx+=x[i];
ansy+=y[i];
}
//srand(114514);
ansx/=m;
srand(20050419);
ansy/=m;
for(int i=1;i<=300;++i)
sa();
printf("The safest point is (%.1lf, %.1lf).\n",ansx,ansy);
}
return 0;
}