首页 > 代码库 > poj1379模拟退火

poj1379模拟退火

  题意: 求一个点到给出点最短距离最长的那个点。

     看rp  迭代次数越多和 初始随机点越多 应该越准确(初始随机点坑了,多了也不一定准确)。

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<time.h>#define eps 1e-4using namespace std;const double maxn = 1e30;const int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };const int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };int bx[2000], by[2000];int X, Y;int gx[105], gy[105];int m;double gao(double x, double y, double x1, double y1){    return sqrt((x - x1)*(x - x1) + (y - y1) *(y - y1));}int gao1(double x, double y){    if (x >= 0 && x <= X&&y >= 0 && y <= Y) return 1;    return 0;}double dis(double x, double y){    double sum = maxn;    for (int i = 0; i < m; i++){        sum = min(sum, gao(x, y, bx[i], by[i]));    }    return sum;}void gaomaoxian(){    double x, y;    double Rand = max(X, Y);    double Max = 0;    for (int i = 0; i < 100; i++){        double dist = dis(gx[i], gy[i]);        if (dist>Max) Max = dist, x = gx[i], y = gy[i];    }    while (Rand>eps){        double xx = x; double yy = y;        for (int i = 0; i < 8; i++){            double x1 = xx + dx[i] * Rand; double y1 = yy + dy[i] * Rand;            if (!gao1(x1, y1))continue;            double dist = dis(x1, y1);            if (dist > Max) Max = dist, x = x1, y = y1;        }        Rand *= 0.99;    }    printf("The safest point is (%.1f, %.1f).\n", x, y);}int main(){    int Icase;    cin >> Icase;    while (Icase--){        cin >> X >> Y >> m;        srand(clock());        for (int i = 0; i < m; i++)            cin >> bx[i] >> by[i];        for (int i = 0; i < 100; i++){            gx[i] = rand() % X; gy[i] = rand() % Y;        }        gaomaoxian();    }    return 0;}

 

poj1379模拟退火