QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#76#17087#55. 欧几里得距离之和JohnAlfnovQingyuSuccess!2022-01-02 18:38:432022-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'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#17087#55. 欧几里得距离之和Qingyu97 7630ms31972kbC++141.9kb2022-01-02 15:46:362022-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);
}