SP34 RUNAWAY - Run Away

Jisoo

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;
}
上一篇:How far away ? HDU


下一篇:萌新web8