模拟退火的第一题~
//By SiriusRen#include#include #include using namespace std;int cases,X,Y,M;struct Point{ double x,y,dis;}point[1005],b[33],ans,t;double dis(Point a){ double tmp=1e8; for(int i=1;i<=M;i++){ double tx=a.x-point[i].x,ty=a.y-point[i].y; tmp=min(tmp,sqrt(tx*tx+ty*ty)); }return tmp;}int main(){ srand(1005730820),scanf("%d",&cases); while(cases--){ scanf("%d%d%d",&X,&Y,&M),ans.dis=0; for(int i=1;i<=M;i++)scanf("%lf%lf",&point[i].x,&point[i].y); for(int i=1;i<=30;i++)b[i].x=rand()%X+1,b[i].y=rand()%Y+1,b[i].dis=dis(b[i]); for(double i=max(X,Y);i>=1e-3;i*=0.9) for(int j=1;j<=30;j++) for(int k=1;k<=30;k++){ double ran=rand(); t.x=b[j].x+cos(ran)*i,t.y=b[j].y+sin(ran)*i,t.dis=dis(t); if(t.x<0||t.x>X||t.y<0||t.y>Y)continue; if(t.dis>b[j].dis)b[j]=t; } for(int i=1;i<=30;i++)if(ans.dis