退火。

const int N = 1e3 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, x[N], y[N], w[N];
	double ansx, ansy, dis;

	mt19937 rnd(time(0));
	double Rand() { return (double)(rnd() % INT_MAX) / INT_MAX; }
	double calc(double xx, double yy) {
		double res = 0;
		for (int i = 1; i <= n; ++i) {
			double dx = x[i] - xx, dy = y[i] - yy;
			res += sqrt(dx * dx + dy * dy) * w[i];
		}
		if (res < dis) dis = res, ansx = xx, ansy = yy;
		return res;
	}
	void simulateAnneal () {
		double t = 100000, curx = ansx, cury = ansy;
		while (t > 0.01) {
			double nxtx = curx + t * (Rand() * 2 - 1);
			double nxty = cury + t * (Rand() * 2 - 1);
			double del = calc(nxtx, nxty) - calc(curx, cury);	
			if (exp(-del / t) > Rand()) curx = nxtx, cury = nxty;
			t *= 0.97;
		}
		for (int i = 1; i <= 1000; ++i) {
			double nxtx = ansx + t * (Rand() * 2 - 1);
			double nxty = ansy + t * (Rand() * 2 - 1);
			calc(nxtx, nxty);
		}
	}
	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) 
			x[i] = Read(), y[i] = Read(), w[i] = Read(), ansx += x[i], ansy += y[i];
		ansx /= n, ansy /= n; dis = calc(ansx, ansy);
		simulateAnneal();
		simulateAnneal();
		printf ("%.3lf %.3lf\n", ansx, ansy);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}
EOF

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。

博客信息

作者
Jayun
时间
2023-11-15 16:39:38