QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#76 | #17087 | #55. 欧几里得距离之和 | JohnAlfnov | Qingyu | Success! | 2022-01-02 18:38:43 | 2022-01-02 18:38:44 |
Details
Extra Test:
Wrong Answer
time: 15ms
memory: 3892kb
input:
4002 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 -3 60 ...
output:
48207037.7134750046
result:
wrong answer 1st numbers differ - expected: '48217654.37668', found: '48207037.71348', error = '0.00022'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#17087 | #55. 欧几里得距离之和 | Qingyu | 97 | 7630ms | 31972kb | C++14 | 1.9kb | 2022-01-02 15:46:36 | 2022-05-04 13:14:41 |
answer
#include <bits/stdc++.h>
const int N = 1e6 + 500;
struct pt {
long double x, y;
} p[N];
int n;
long double x[N];
std::mt19937 s(std::chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) {
return std::uniform_int_distribution<int>(l, r)(s);
}
template <int T>
struct fast_io
{
char *p1, *p2, *q1, *q2, p[T], q[T];
fast_io()
{
p1 = p2 = p, q1 = q, q2 = q + T;
}
inline char gc()
{
return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
}
inline void pc(char ch)
{
if (q1 == q2)
{
fwrite(q, 1, T, stdout);
q1 = q;
}
*q1++ = ch;
}
~fast_io()
{
fwrite(q, 1, q1 - q, stdout);
}
};
fast_io<1024768> io;
inline int read()
{
int res = 0, neg = 1;
char ch;
do {
ch = io.gc();
if (ch == '-') neg = -1;
} while (ch < 48 || ch > 57);
do res = res * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
return res * neg;
}
const long double pi = acosl(-1.0L);
int main() {
std::ios::sync_with_stdio(false);
n = read();
long double min = 1e9;
for (int i = 1; i <= n; ++i) {
p[i].x = read();
p[i].y = read();
min = std::min(p[i].y, min);
}
for (int i = 1; i <= n; ++i) {
p[i].y -= min;
}
if (n <= 4000) {
double ans = .0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
ans += std::sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
}
}
printf("%.10f\n", ans);
return 0;
}
long double ans = 0.0;
const int Z = 130;
for (int _ = 0; _ < Z; ++_) {
long double theta = 2 * pi * _ / Z;
long double s = std::sin(theta), c = std::cos(theta);
for (int i = 1; i <= n; ++i) {
x[i] = (p[i].x * c - p[i].y * s);
}
std::sort(x + 1, x + n + 1);
long double sum = 0;
for (int i = 1; i <= n; ++i) {
ans += (i - 1) * x[i] - sum;
sum += x[i];
}
}
printf("%.10Lf\n", ans / Z * pi / 2);
}