记录编号	390111	评测结果	WWWAWWAW
题目名称	[CEOI1999][POJ1379]逃离陷阱	最终得分	25
用户昵称	yourfather	是否通过	未通过
代码语言	C++	运行时间	0.245 s
提交时间	2017-04-01 21:09:07	内存使用	0.31 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
const int SIZEN = 1010;
const double MIN_T = 1e-6;
const double C = 0.99;
const double PI (acos(-1));
struct Point{
	double x,y;
	Point(){x = 0;y = 0;}
	Point(double _x,double _y):
	x(_x),y(_y){}
	void read(){scanf("%lf%lf",&x,&y);}
	Point operator + (const Point &a)const
	{return Point(x+a.x,y+a.y);}
	Point operator / (const int &a)const
	{return Point(x/a,y/a);}
	void Print()
	{printf("The safest point is (%.1f, %.1f).\n",x,y);}
}p[SIZEN],nw,nt;
int M,X,Y;
double ans = -1;
Point ansp;
double Random()
{return (rand()%1000+1)/1000.0;}
double dist(Point A,Point B)
{return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
double Calc(Point P){
	double ret = 1e30;
	for(int i = 1;i <= M;i++)ret = min(ret,dist(P,p[i]));
	if(ret > ans){ans = ret,ansp = P;}
	return ret;
}
bool Check(Point P){
	if(P.x < 0||P.y < 0||P.x > X||P.y > Y)return false;
	return true;
}
void Search(){
	double T = 1e4;
	nw = Point(rand()%X+1,rand()%Y+1);
	while(T > MIN_T){
		double rad = 2.0*Random()*PI;
		nt = Point(nw.x+T*cos(rad),nw.y+T*sin(rad));
		if(Check(nt)){
			double dT = Calc(nt) - Calc(nw);
			if(dT >= 0||exp(dT/T) >= Random())nw = nt;
		}
		T = T*C;
	}
	for(int i = 1;i <= 5000;i++){
		double rad = 2.0*Random()*PI;
		nt = Point(ansp.x+cos(rad),ansp.y+sin(rad));
		if(Check(nt))Calc(nt);
		else i--;
	}
	ansp.Print();
}
int main(){
	freopen("runaway.in","r",stdin);
	freopen("runaway.out","w",stdout);
	srand(time(0));
	scanf("%d%d%d",&X,&Y,&M);
	for(int i = 1;i <= M;i++)p[i].read();
	Search();
	return 0;
}