AcWing 3167. 星星还是树
原题链接
中等
作者:
能鸽善武
,
2022-02-15 20:14:31
,
所有人可见
,
阅读 203
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../template/debug.h"
#else
#define debug(...) 42
#endif
using pdd = pair<double, double>;
double get(const pdd &a, const pdd &b) {
double dx = a.first - b.first;
double dy = a.second - b.second;
return sqrt(dx * dx + dy * dy);
}
double rand(double l, double r) {
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
return (double) rng() / numeric_limits<unsigned int>::max() * (r - l) + l;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<pdd> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
double ans = 1e18;
auto calc = [&](const pdd &x) {
double res = 0;
for (int i = 0; i < n; ++i) {
res += get(a[i], x);
}
ans = min(ans, res);
return res;
};
auto SA = [&]() {
pdd rp = {rand(0, 10000), rand(0, 10000)};
for (double t = 1e4; t > 1e-4; t *= 0.94) {
double x = rp.first, y = rp.second;
pdd new_p = {rand(x - t, x + t), rand(y - t, y + t)};
double dt = calc(new_p) - calc(rp);
if (exp(-dt / t) > rand(0, 1)) {
rp = new_p;
}
}
};
for (int it = 0; it < 50; ++it) {
SA();
}
cout << fixed << setprecision(0) << ans << '\n';
return 0;
}