#include <stdio.h>int main(){puts("转载请注明出处[vmurder]谢谢");puts("网址：blog.csdn.net/vmurder/article/details/43526827");}
题意：
给若干个点，现在求一个点，使它到离它最近的点尽量远。
题解：
我写的是模拟退火先玩一会，然后小幅度爬爬山。
种子的采用是20134858
是生日^人的名字首字母hash。
诶可算A了，看来我脸还不是太黑。
代码：
#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 10100#define dinf 1e18#define eps 1e-5#define down 0.998using namespace std;double n,m;struct Point // 点{double x,y,z; // 坐标、该点作为结束点的答案。Point(double _x=0.0,double _y=0.0):x(_x),y(_y){}bool in(){if(x<0.0||x>n)return 0;if(y<0.0||y>m)return 0;return 1;}}P[N],now,ans;int p;// 随机函数，，随机出来一个0~1之间的小数inline double Rand(){return ((double)(rand()%1000+1.0))/1000.0;}// 其实找初始点时最好找平均数之类inline void init() {double tempx=0.0,tempy=0.0;for(int i=1;i<=p;i++)tempx+=P[i].x,tempy+=P[i].y;tempx+=2*n,tempy+=2*m;now=Point(tempx/(p+4),tempy/(p+4));//now=Point(n/2,m/2);ans.z=0.0;}// 计算两点间欧拉距离inline double calc(const Point &a,const Point &b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}// 计算所有点到点a的欧拉距离最小值并更新ansinline double Calc(Point &a){a.z=dinf;for(int i=1;i<=p;i++)a.z=min(a.z,calc(P[i],a));if(a.z>ans.z)ans=a;return a.z;}Point newpos(double T,const Point &a){double alp=2.0*acos(-1.0)*Rand(); // 角度return Point(a.x+T*cos(alp)*Rand(),a.y+T*sin(alp)*Rand());}// 模拟退火void Std_Anne() // [S]imula[t]e[d] [Anne]aling{ // 温度，或者说转移半径for(double T=sqrt(n*n+m*m)*0.42;T>eps;T*=down) // 每次降温{Point next=newpos(T,now);// next为转移后的点if(next.in()){double dis=Calc(next)-Calc(now);if(exp(dis/T)>Rand()-eps)now=next;}}}// 爬山void ioi() // Cl[i]mb M[o]unta[i]n{double T=0.5,alp;for(int i=1;i<=50000;i++){Point next=newpos(T,ans);if(next.in()){double dis=Calc(next)-Calc(now);if(dis>0)now=next;}}}int main(){freopen("test.in","r",stdin);srand(20134858);int i,j,k,g;for(scanf("%d",&g);g–;){scanf("%lf%lf%d",&n,&m,&p);for(i=1;i<=p;i++)scanf("%lf%lf",&P[i].x,&P[i].y);init();Std_Anne();ioi();printf("The safest point is (%.1lf, %.1lf).\n",ans.x,ans.y);}return 0;}
学习会使你永远立于不败之地。
