首页 > 代码库 > POJ 1379 Run Away 【基础模拟退火】

POJ 1379 Run Away 【基础模拟退火】

题意:找出一点,距离所有所有点的最短距离最大

二维平面内模拟退火即可,同样这题用最小圆覆盖也是可以的。

 

Source Code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <fstream>#include <cstring>#include <cmath>#include <stack>#include <string>#include <map>#include <queue>#include <vector>#include <ctime>#include <algorithm>#define LL long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))#define MOD 1000000007#define eps 1e-8#define pi acos(-1.0)using namespace std;const int inf = 0x3f3f3f3f;const int N = 15;const int L = 35;int t,n;double X ,Y, best[50];struct Point{    double x,y;    bool check(){        if(x > -eps && x < eps + X && y > -eps && y < eps + Y)            return true;        return false;    }}p[1005],tp[50];double dist(Point p1,Point p2){    return sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y));}double min_dis(Point p0){    double ans = inf;//    for(int i = 0; i < n; ++i)        ans = min(ans,dist(p[i],p0));//    return ans;}Point rand_point(double x, double y){    Point c;    c.x = (rand() % 1000 + 1) / 1000.0 * x;    c.y = (rand() % 1000 + 1) / 1000.0 * y;    return c;}int main(){    srand(time(NULL));    scanf("%d",&t);    while(t--){        scanf("%lf%lf%d",&X,&Y,&n);        for(int i = 0; i < n; ++i)            scanf("%lf%lf",&p[i].x,&p[i].y);        for(int i = 0; i < N; ++i){            tp[i] = rand_point(X, Y);            best[i] = min_dis(tp[i]);        }        double step = max(X,Y) / sqrt(1.0 * n);        while(step > 1e-3){            for(int i = 0; i < N; ++i){                Point cur;                Point pre = tp[i];                for(int j = 0; j < L; ++j){                    double angle = (rand() % 1000 + 1) / 1000.0 * 2 * pi;                    cur.x = pre.x + cos(angle) * step;                    cur.y = pre.y + sin(angle) * step;                    if(!cur.check()) continue;                    double tmp = min_dis(cur);                    if(tmp > best[i]){//                        tp[i] = cur;                        best[i] = tmp;                    }                }            }            step *= 0.85;        }        int idx = 0;        for(int i = 0; i < N; ++i){            if(best[i] > best[idx]){//                idx = i;            }        }        printf("The safest point is (%.1f, %.1f).\n",tp[idx].x,tp[idx].y);        //printf("%.1f\n",best[idx]);    }    return 0;}

 

POJ 1379 Run Away 【基础模拟退火】