• 问答
• ## 关于 Hydro OJ 的评测速度

• @ 2021-6-3 9:40:01

``````/*
I will never forget it.
*/

// 392699

#include <bits/stdc++.h>

using namespace std;

void fr(int &a, bool f = 0, char ch = getchar()) {
for (a = 0; ch < '0' || ch > '9'; ch = getchar()) ch == '-' ? f = 1 : 0;
for (; ch >= '0' && ch <= '9'; ch = getchar()) a = a * 10 + ch - '0';
a = f ? -a : a;
}
int fr() {
int a;
return fr(a), a;
}

const int N = 1e4;
const double alpha = 0.974, eps = 1e-7;

int n;
double ansx, ansy, ansd, x[N + 10], y[N + 10], w[N + 10];

double dist(double xa, double ya, double xb, double yb) { return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb)); }

double calc(double tx, double ty) {
double res = 0;
for (int i = 1; i <= n; i++) res += dist(x[i], y[i], tx, ty) * w[i];
if (res < ansd) ansd = res, ansx = tx, ansy = ty;
return res;
}

double rnd() { return (double)rand() / RAND_MAX; }

void SimulateAnneal() {
double temp = 2e3, nowx = ansx, nowy = ansy;
while (temp > eps) {
double tx = nowx + temp * (rnd() * 2 - 1), ty = nowy + temp * (rnd() * 2 - 1);
double delta = calc(tx, ty) - calc(nowx, nowy);
if (delta < 0 || rnd() < exp(-delta / temp)) nowx = tx, nowy = ty;
temp *= alpha;
}
}

struct OI {
int RP, score;
} CSPS2021, NOIP2021;

int main() {
CSPS2021.RP++, CSPS2021.score++, NOIP2021.RP++, NOIP2021.score++, 392699;
srand(999392699);
fr(n);
for (int i = 1; i <= n; i++) scanf("%lf%lf%lf", &x[i], &y[i], &w[i]), ansx += x[i], ansy += y[i];
ansx /= n, ansy /= n, ansd = calc(ansx, ansy);
for (int i = 1; i <= 5; i++) SimulateAnneal();
for (int i = 1; i <= 7000; i++) {
double tx = ansx + 0.001 * (rnd() * 2 - 1), ty = ansy + 0.001 * (rnd() * 2 - 1);
calc(tx, ty);
}
return printf("%.3lf %.3lf\n", ansx, ansy), 0;
}
``````