POJ-1379 Run Away
题意： 平面上给定n个点， 要求找到一个点使得到所有点的距离最大。
分析： 模拟退火， 计算到每个点的最小距离， 使得最小距离最大。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>using namespace std;const int MAXN = 1111;
const double eps = 1e-9;
const double inf = 0x3f3f3f3f;
struct Point
{
double x, y;double distance (Point b){
return hypot (x - b.x, y - b.y);}
};Point pp[MAXN];int dx[] = {
0, 0, 1, 1, -1, -1, 1, -1};
int dy[] = {
1, -1, -1, 1, 1, -1, 0, 0};
double mindis (int n, Point now)
{
double res = inf;for (int i = 0; i < n; i++){
res = min (res, now.distance(pp[i]));}return res;
}
int main ()
{
int t;scanf ("%d", &t);while (t--){
double X, Y;int n;scanf ("%lf%lf%d", &X, &Y, &n);for (int i = 0; i < n; i++)scanf ("%lf%lf", &pp[i].x, &pp[i].y);double step = 100000, r = 0.9;double x = 0, y = 0;Point now;now.x = x, now.y = y;double ans = mindis(n, now);while (step > eps){
double checkx = x, checky = y, checkans = ans;for (int i = 0; i < 8; i++){
now.x = x + step*dx[i];now.y = y + step*dy[i];if (now.x >=0 && now.x < X + eps && now.y >= 0 && now.y < Y + eps){
double tmp = mindis (n, now);if (tmp > checkans){
checkx = now.x;checky = now.y;checkans = tmp;}}}x = checkx;y = checky;ans = checkans;step*=r;}printf ("The safest point is (%.1f, %.1f).\n", x, y);}return 0;
}