QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#72 | #16835 | #55. 欧几里得距离之和 | JohnAlfnov | Qingyu | Failed. | 2022-01-02 13:14:32 | 2022-01-02 13:14:34 |
Details
Extra Test:
Accepted
time: 1ms
memory: 9716kb
input:
20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
output:
26.8707115346
result:
ok found '26.87071', expected '26.87006', error '0.00002'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#16835 | #55. 欧几里得距离之和 | Qingyu | 97 | 8111ms | 41128kb | C++14 | 1.7kb | 2021-12-24 00:16:20 | 2022-05-04 11:57:33 |
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);
std::pair<long double, int> id[N];
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();
id[i].first = 0;
id[i].second = i;
}
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) {
id[i].first = p[id[i].second].x * c - p[id[i].second].y * s;
}
std::sort(id + 1, id + n + 1);
long double sum = 0;
for (int i = 1; i <= n; ++i) {
ans += (i - 1) * id[i].first - sum;
sum += id[i].first;
}
}
printf("%.10Lf\n", ans / Z * pi / 2);
}