poj1379

poj1379

题意

给出 n 个洞的坐标，要求找到一点使得这一点距离最近洞的距离最远。

分析

通过这道题学习一下模拟退火算法，

这种随机化的算法，在求解距离且精度要求较小时很有用。

简而言之，由随机选取的多个初始点，进行多次的随机变换，并根据是否更优而选择是否保留答案，

那么首先要选择两个值，delta 表示初始最大变换的半径（即对应初始的火温），d 控制半径缩小的快慢（火温减小的快慢）。

这道题，比较直白，随机变换就是改变坐标的位置（通过半径和角度就可以变换坐标，当然角度也是随机的），若变换后距所有点的距离增大了那么则更优。

code

#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 1005;
const int MAXP = 20; // 随机选取 20 个点
const double PI = acos(-1.0);
double X, Y;
int n;
double dis[100];
struct P
{double x, y;P() {}P(double _x, double _y) : x(_x), y(_y) {}P operator - (P p){return P(x - p.x, y - p.y);}double dis(){return sqrt(x * x + y * y);}
}a[MAXN], ans[MAXN];
double getMinDis(P p)
{double as = 1e9;for(int i = 0; i < n; i++){as = min(as, (p - a[i]).dis());}return as;
}
P SA()
{for(int i = 0; i < MAXP; i++){ans[i].x = (rand() % 1000 + 1) / 1000.0 * X;ans[i].y = (rand() % 1000 + 1) / 1000.0 * Y;dis[i] = getMinDis(ans[i]);}double delta = max(X, Y) / sqrt(n * 1.0), d = 0.9;while(delta > 0.01) // 边界最小值{for(int i = 0; i < MAXP; i++){for(int j = 0; j < 20; j++){P t = ans[i];double angle = rand() % 1000 / 1000.0 * 2 * PI;t.x += delta * cos(angle) * (rand() % 1000 / 1000.0);t.y += delta * sin(angle) * (rand() % 1000 / 1000.0);if(t.x < 0 || t.x > X || t.y < 0 || t.y > Y)  continue;double tmp = getMinDis(t);if(tmp > dis[i]){dis[i] = tmp;ans[i] = t;}}}delta *= d;}double dd = 0;int pp = 0;for(int i = 0; i < MAXP; i++){if(dis[i] > dd){dd = dis[i];pp = i;}}return ans[pp];
}
int main()
{srand(time(0));int T;for(scanf("%d", &T); T--;){scanf("%lf%lf%d", &X, &Y, &n);for(int i = 0; i < n; i++){scanf("%lf%lf", &a[i].x, &a[i].y);}P p = SA();printf("The safest point is (%.1f, %.1f).\n", p.x, p.y);}return 0;
}

转载于:https://www.cnblogs.com/ftae/p/6844715.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！