QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#72#16835#55. 欧几里得距离之和JohnAlfnovQingyuFailed.2022-01-02 13:14:322022-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'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#16835#55. 欧几里得距离之和Qingyu97 8111ms41128kbC++141.7kb2021-12-24 00:16:202022-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);
}