退火。
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