QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#75 | #16834 | #55. 欧几里得距离之和 | JohnAlfnov | Qingyu | Success! | 2022-01-02 13:35:26 | 2022-01-02 13:35:26 |
详细
Extra Test:
Wrong Answer
time: 16ms
memory: 7780kb
input:
4002 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3 ...
output:
34204662.0316304410
result:
wrong answer 1st numbers differ - expected: '34208903.03667', found: '34204662.03163', error = '0.00012'
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#16834 | #55. 欧几里得距离之和 | Qingyu | 97 | 8229ms | 30508kb | C++14 | 1.8kb | 2021-12-24 00:09:27 | 2022-05-04 11:54:51 |
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();
for (int i = 1; i <= n; ++i) {
p[i].x = read();
p[i].y = read();
}
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 = 140;
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);
}