基础模拟退火。
/* poj 1379 */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; #define MAXN 1005
#define INF 999999
#define MAXM 25 typedef struct {
double x, y;
} Point_t; const double eps = 1e-;
const double next = 0.9;
const double PI = acos(-1.0);
double X, Y;
int n;
Point_t points[MAXN];
Point_t rpoints[MAXM];
double rdis[MAXM]; inline bool check(Point_t p) {
return p.x< || p.x>=X || p.y< || p.y>=Y;
} double cross(Point_t a, Point_t b, Point_t c) {
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
} double Length(Point_t a, Point_t b) {
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
} double solve(Point_t p) {
int i, j, k;
double ret = INF; for (i=; i<n; ++i) {
ret = min(ret, Length(p, points[i]));
} return ret;
} int main() {
int t;
int i, j, k;
Point_t p, pp;
double step, angle;
double ans, tmp; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif scanf("%d", &t);
while (t--) {
scanf("%lf %lf %d", &X, &Y, &n);
for (i=; i<n; ++i)
scanf("%lf %lf", &points[i].x, &points[i].y);
for (i=; i<MAXM; ++i) {
rpoints[i].x = (rand()%+)/1000.0*X;
rpoints[i].y = (rand()%+)/1000.0*Y;
rdis[i] = solve(rpoints[i]);
}
step = max(X, Y)/sqrt(1.0*n);
while (step > eps) {
for (i=; i<MAXM; ++i) {
p = rpoints[i];
for (j=; j<MAXM; ++j) {
angle = (rand()%+)/.**PI;
pp.x = p.x + cos(angle)*step;
pp.y = p.y + sin(angle)*step;
if (check(pp))
continue;
tmp = solve(pp);
if (tmp > rdis[i]) {
rpoints[i] = pp;
rdis[i] = tmp;
}
}
}
step *= next;
}
double ans = -1.0;
k = ;
for (i=; i<MAXM; ++i) {
if (rdis[i] > ans) {
ans = rdis[i];
k = i;
}
}
printf("The safest point is (%.1lf, %.1lf).\n", rpoints[k].x, rpoints[k].y);
} return ;
}