1 /* poj 1379 */  2 #include <iostream>  3 #include <cstdio>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cmath>  7 #include <algorithm>  8 using namespace std;  9  10 #define MAXN 1005 11 #define INF     999999 12 #define MAXM 25 13  14 typedef struct { 15     double x, y; 16 } Point_t; 17  18 const double eps = 1e-3; 19 const double next = 0.9; 20 const double PI = acos(-1.0); 21 double X, Y; 22 int n; 23 Point_t points[MAXN]; 24 Point_t rpoints[MAXM]; 25 double rdis[MAXM]; 26  27 inline bool check(Point_t p) { 28     return p.x<0 || p.x>=X || p.y<0 || p.y>=Y; 29 } 30  31 double cross(Point_t a, Point_t b, Point_t c) { 32     return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y); 33 } 34  35 double Length(Point_t a, Point_t b) { 36     return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); 37 } 38  39 double solve(Point_t p) { 40     int i, j, k; 41     double ret = INF; 42      43     for (i=0; i<n; ++i) { 44         ret = min(ret, Length(p, points[i])); 45     } 46      47     return ret; 48 } 49  50 int main() { 51     int t; 52     int i, j, k; 53     Point_t p, pp; 54     double step, angle; 55     double ans, tmp; 56      57     #ifndef ONLINE_JUDGE 58         freopen("data.in", "r", stdin); 59     #endif 60      61     scanf("%d", &t); 62     while (t--) { 63         scanf("%lf %lf %d", &X, &Y, &n); 64         for (i=0; i<n; ++i) 65             scanf("%lf %lf", &points[i].x, &points[i].y); 66         for (i=0; i<MAXM; ++i) { 67             rpoints[i].x = (rand()%1000+1)/1000.0*X; 68             rpoints[i].y = (rand()%1000+1)/1000.0*Y; 69             rdis[i] = solve(rpoints[i]); 70         } 71         step = max(X, Y)/sqrt(1.0*n); 72         while (step > eps) { 73             for (i=0; i<MAXM; ++i) { 74                 p = rpoints[i]; 75                 for (j=0; j<MAXM; ++j) { 76                     angle = (rand()%1000+1)/1000.*10*PI; 77                     pp.x = p.x + cos(angle)*step; 78                     pp.y = p.y + sin(angle)*step; 79                     if (check(pp)) 80                         continue; 81                     tmp = solve(pp); 82                     if (tmp > rdis[i]) { 83                         rpoints[i] = pp; 84                         rdis[i] = tmp; 85                     } 86                 } 87             } 88             step *= next; 89         } 90         double ans = -1.0; 91         k = 0; 92         for (i=0; i<MAXM; ++i) { 93             if (rdis[i] > ans) { 94                 ans = rdis[i]; 95                 k = i; 96             } 97         } 98         printf("The safest point is (%.1lf, %.1lf).\n", rpoints[k].x, rpoints[k].y); 99     }100     101     return 0;102 }