QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1194 | #611826 | #9289. 1%-Euclidean | N_z_ | Yzm007 | Success! | 2024-11-18 16:43:27 | 2024-11-18 16:43:28 |
详细
Extra Test:
Wrong Answer
time: 634ms
memory: 10892kb
input:
500000 -1000000 -1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 100...
output:
1467243636468.94873
result:
wrong answer error = 0.03754 (3.75379e-02)
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#611826 | #9289. 1%-Euclidean | Yzm007 | WA | 668ms | 11248kb | C++14 | 1.3kb | 2024-10-04 22:59:08 | 2024-11-18 16:50:10 |
answer
// https://codeforces.com/gym/104848/problem/I
#include <bits/stdc++.h>
#define fore(i, a, b) for (ll i = a, gmat = b; i < gmat; i++)
#define FIN ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
#pragma GCC optimize("Ofast")
double dist(ii p0, ii p1) {
auto [x0, y0] = p0;
auto [x1, y1] = p1;
return sqrt((double)((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)));
}
const ll total = 4e7;
double solve(const vii& ps) {
ll n = ps.size();
if (n*n <= total) {
double ans = 0.0;
fore(i, 0, n) {
fore(j, i + 1, n) {
ans += dist(ps[i], ps[j]);
}
}
return ans;
} else {
double ans = 0.0;
static random_device rd;
static mt19937_64 gen(rd());
uniform_int_distribution<ll> dis(0, n - 1);
fore(_, 0, total) {
ll i = dis(gen), j = dis(gen);
if (i != j) {
ans += dist(ps[i], ps[j]);
}
}
ans *= ((double)(n * (n - 1))) / ((double)(2*total));
return ans;
}
}
int main() {
FIN;
ll n;
cin >> n;
vii ps(n);
for (auto& [x, y] : ps) {
cin >> x >> y;
}
cout << setprecision(5) << fixed;
cout << solve(ps) << '\n';
return 0;
}