欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

杭电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 杭电OJ