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

亦凉 2021-12-10 16:39 215阅读 0赞

题意：找出一点，距离所有所有点的最短距离最大

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

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;
    }

转载于:https://www.cnblogs.com/wushuaiyi/p/4242426.html