随机化

随机数生成器

mt19937 Rand(random_device{}());

模拟退火

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e3 + 10;
/*====================*/
double begintime = 0;
bool TLE(void)
{
	if ((clock() - begintime) / CLOCKS_PER_SEC > 0.9)
	{
		return true;
	}
	return false;
}
/*====================*/
int n;
/*====================*/
struct Node
{
	double w, x, y;
	Node(double _w = 0, double _x = 0, double _y = 0)
	{
		w = _w, x = _x, y = _y;
	}
};
Node node[N];
/*====================*/
double ansx, ansy, ansSigma = 1e18;
/*====================*/
double GetSigma(double x, double y)
{
	double res = 0;
	for (int i = 1; i <= n; ++i)
	{
		double dx = node[i].x - x;
		double dy = node[i].y - y;
		res += sqrt(dx * dx + dy * dy) * node[i].w * 100;
	}
	if (res < ansSigma)
	{
		ansx = x, ansy = y, ansSigma = res;
	}
	return res;
}
/*====================*/
double Rand() { return (double)rand() / RAND_MAX; }
/*====================*/
void SA(void)
{
	double curx = 0, cury = 0, curSigma = 0;
	for (int i = 1; i <= n; ++i)
	{
		curx += node[i].x, cury += node[i].y;
	}
	curx /= n, cury /= n; curSigma = GetSigma(curx, cury);

	double t = 1e4;
	while (t > 5e-4)
	{
		double nxtx = curx + t * (Rand() * 2.0 - 1.0);
		double nxty = cury + t * (Rand() * 2.0 - 1.0);
		double nxtSigma = GetSigma(nxtx, nxty);
		double delta = nxtSigma - curSigma;
		if (exp(-delta / t) > Rand())
		{
			curx = nxtx, curx = nxty, curSigma = nxtSigma;
		}
		t *= 0.9996;
	}
	for (int i = 1; i <= 5000; ++i) 
	{
		double nxtx = ansx + t * (Rand() * 2 - 1);
		double nxty = ansy + t * (Rand() * 2 - 1);
		double nxtSigma = GetSigma(nxtx, nxty);
	}
}
/*====================*/
void Solve(void)
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		double w, x, y;
		cin >> x >> y >> w;
		node[i] = Node(w, x, y);
	}
	while (!TLE())SA();
	printf("%.3f %.3f\n", ansx, ansy);
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	srand(time(0)); begintime = clock();
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}