首页 > 代码库 > 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模拟退火
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。