杭电OJ 1109(C++)
程序员文章站
2022-07-13 17:38:06
...
#include <iostream>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
const int MAXN = 1505;
const int NUM = 30; //随机选择的初始点的数量
const double exps = 1e-3; //精度
const double pi = acos(-1.0); //圆周率Π
double PX[MAXN], PY[MAXN]; //陷阱的X坐标和Y坐标
double fx[MAXN], fy[MAXN], best[MAXN]; //随机选择的点的坐标和到达最近陷阱的距离
//在区间内生成随机数
double Rand(double L, double R)
{
return (rand() % 10000) / 10000.0 * (R - L) + L;
}
//计算两点间的距离
double dist(double x1, double y1, double x2, double y2)
{
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main()
{
int T, X, Y, n;
cin >> T;
srand(time(0));
while (T--)
{
cin >> X >> Y >> n;
for (int i = 1; i <= n; i++)
{
cin >> PX[i] >> PY[i];
}
for (int i = 1; i <= NUM; i++) //随机NUM个初始点,进行模拟退火
{
fx[i] = Rand(1, X);
fy[i] = Rand(1, Y);
best[i] = INT_MAX;
for (int j = 1; j <= n; j++)
{
//评估函数,评估整个退火过程的好坏
best[i] = min(best[i], dist(fx[i], fy[i], PX[j], PY[j]));
}
}
double step = max(X, Y); //最长跨度
while (step > exps)
{
for (int i = 1; i <= NUM; i++)
{
for (int j = 1; j <= NUM; j++)
{
double angel = Rand(0, 2 * pi); //枚举任意角度,使得到的新点向四周扩散
double nx = fx[i] + cos(angel) * step;
double ny = fy[i] + sin(angel) * step;
if (nx < 0 || nx > X || ny < 0 || ny > Y)
continue;
double d = INT_MAX;
for (int k = 1; k <= n; k++)
{
d = min(d, dist(nx, ny, PX[k], PY[k]));
}
if (d > best[i])
{
best[i] = d;
fx[i] = nx;
fy[i] = ny;
}
}
}
step *= 0.85; //退火
}
int t = 1;
for (int i = 1; i <= NUM; i++)
{
if (best[i] >= best[t])
t = i;
}
cout << "The safest point is ("
<< fixed << setprecision(1) << fx[t] << ", "
<< fy[t] << ")." << endl;
}
return 0;
}
上一篇: 杭电OJ 1100(C++)
下一篇: 杭电OJ 1131(C++)