[文章目录]
Description
题目看不懂，看sample懂了。就是给你一个X*Y的网格图，X,Y<=10000，然后给你m个点,m<=1000，问你与m个点的欧几里得距离的最小值最大的点的坐标。多组数据T<=10。
随机化，想平面上随机撒点，然后每个点进行爬山算法，将步长由大趋近于0。看步长可及的解是否比原解更优，如果优于原解则更新出发点。当步长趋于0时，解稳定在一个范围里。进行多次随机。更新最后的解。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int T,X,Y,m;
double mi,ansx,ansy,ans;
struct node
{
int x,y;
}a[1100];
double dis(double x,double y,int id)
{
return (x-a[id].x)*(x-a[id].x)+(y-a[id].y)*(y-a[id].y);
}
double lim(double x,double y)//更新原解
{
if(x>X||y>Y||x<0||y<0) return 0.0;
double re=100000000.0;
for(int i=1;i<=m;i++)
{
double tmp=dis(x,y,i);
if(tmp<re) re=tmp;
}
return re;
}
void check(double d,double &x,double &y)
{
double temp=lim(x+d,y+d),tmp,tx=x+d,ty=y+d;
tmp=lim(x-d,y+d); if(tmp>temp) temp=tmp,tx=x-d,ty=y+d;
tmp=lim(x-d,y-d); if(tmp>temp) temp=tmp,tx=x-d,ty=y-d;
tmp=lim(x+d,y-d); if(tmp>temp) temp=tmp,tx=x+d,ty=y-d;
if(temp>mi) mi=temp,x=tx,y=ty;
}
int main()
{
scanf("%d",&T);
while(T--)
{
ans=mi=0;
scanf("%d%d%d",&X,&Y,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&a[i].x,&a[i].y);
int t=100000/m;
while(t--)
{
double tmp=1.0*(X+Y);
double x=rand()%X+1.0,y=rand()%Y+1.0;
while(tmp>=1e-4)
{
check(tmp,x,y);
tmp*=0.5;//将步长减小
}
if(mi>ans) ans=mi,ansx=x,ansy=y;
}
printf("The safest point is (%.1lf, %.1lf).\n",ansx,ansy);
}
return 0;
}