洛谷 [P1337] 平衡点

模拟退火练手

一道模拟退火的好题

结果一定势能最小

与模拟退火思路高度一致

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#include <ctime>

using namespace std;

const int MAXN = 1005;

struct point {

	double x, y, wei;

}poor[MAXN];

int n;

const double delta = 0.993;

const double eps = 1e-14;

double xans, yans, ans = 1e15, best = 1e15;

double energy(double x, double y) {

	double tot = 0.0;

	for(int i = 1; i <= n; i++) {

		tot += sqrt((poor[i].x - x) * (poor[i].x - x) + (poor[i].y - y) * (poor[i].y - y)) * poor[i].wei;

	}

	return tot;

}

double RAND(double T) {

	return (rand() * 2 - RAND_MAX) * T;

}

void solve() {

	double T = 10000.0;

	best = ans = energy(xans, yans);

	double xx = xans, yy = yans;

	while(T > eps) {

		double xt = xx + RAND(T);

		double yt = yy + RAND(T);

		double anst = energy(xt, yt);

		double DE = ans - anst;

		if(DE > 0.0) {

			xx = xt; yy = yt;

			ans = anst;

			if(ans < best) {

				xans = xx; yans = yy;

				best = ans;

			}

		} else if(exp(DE / T) * RAND_MAX > (double)rand()) {

			xx = xt; yy = yt;ans = anst;

		}

		T *= delta;

	}

}

int main() {

	srand(time(NULL));

	cin >> n;

	for(int i = 1; i <= n; i++) {

		cin >> poor[i].x >> poor[i].y >> poor[i].wei;

		xans += poor[i].x; yans += poor[i].y;

	}

	xans /= (double)n; yans /= (double)n;

	solve();

	solve();

	solve();

	printf("%.3f %.3f\n", xans, yans);

	return 0;

}