题意：平面上找一个点，使得其到给定的n个点的距离的最小值最大。
模拟退火看这篇：http://www.cnblogs.com/autsky-jadek/p/7524208.html
这题稍有不同之处仅有：多随机几个初始点，以增加正确率。
另：WA了几百遍竟然是因为最后输出了-0.0这样的值……
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const double EPS=0.00000001;
const double PI=acos(-1.0);
struct Point{
double x,y;
Point(const double &x,const double &y){
this->x=x;
this->y=y;
}
Point(){}
void read(){
scanf("%lf%lf",&x,&y);
}
double length(){
return sqrt(x*x+y*y);
}
}a[1005],p,allp;
double ans,allans;
int n,X,Y;
typedef Point Vector;
Vector operator - (const Point &a,const Point &b){
return Vector(a.x-b.x,a.y-b.y);
}
Vector operator + (const Vector &a,const Vector &b){
return Vector(a.x+b.x,a.y+b.y);
}
Vector operator * (const double &K,const Vector &v){
return Vector(K*v.x,K*v.y);
}
double calc(Point p){
double res=1000000.0;
for(int i=1;i<=n;++i){
res=min(res,(a[i]-p).length());
}
return res;
}
int main(){
int zu;
srand(233);
//freopen("poj1379.in","r",stdin);
//freopen("poj1379.out","w",stdout);
scanf("%d",&zu);
for(;zu;--zu){
allans=0.0;
scanf("%d%d%d",&X,&Y,&n);
p=Point(0.0,0.0);
for(int i=1;i<=n;++i){
a[i].read();
}
for(int j=1;j<=15;++j){
p.x=(double)(rand()%(X+1));
p.y=(double)(rand()%(Y+1));
ans=calc(p);
double T=sqrt((double)X*(double)X+(double)Y*(double)Y)/2.0;
// double T=(double)max(X,Y)/sqrt((double)n);
while(T>EPS){
double bestnow=0.0;
Point besttp;
for(int i=1;i<=35;++i){
double rad=(double)(rand()%10000+1)/10000.0*2.0*PI;
Point tp=p+T*Point(cos(rad),sin(rad));
if(tp.x>-EPS && tp.x-(double)X<EPS && tp.y>-EPS && tp.y-(double)Y<EPS){
double now=calc(tp);
if(now>bestnow){
bestnow=now;
besttp=tp;
}
}
}
if(bestnow>EPS && (bestnow>ans || exp((bestnow-ans)/T)*10000.0>(double)(rand()%10000))){
ans=bestnow;
p=besttp;
}
T*=0.9;
}
if(ans>allans){
allans=ans;
allp=p;
}
}
printf("The safest point is (%.1f, %.1f).\n",fabs(allp.x),fabs(allp.y));
}
return 0;
}