A Bite of Teyvat

The first line contains an integer $n$ $(1 \le n \le 10^5)$ , indicating the number of plates Xiangling has bought.

Then follow $n$ lines, the $i$ -th of which contains two integers $x_i$ $(-10^5 \le x_i \le 10^5)$ and $r_i$ $(1 \le r_i \le 10^6)$ , indicating that the $i$ -th plate placed by Guoba has radius $r_i$ and the center of this plate locates at $(x_i, 0)$ on the table.

Output $n$ lines, the $i$ -th of which contains a real number, indicating the total area covered by the plates on the table after Guoba places the first $i$ -th plates.

Your answer is acceptable if its absolute or relative error does not exceed $10^{-9}$ . Formally speaking, suppose that your output is $x$ and the jury's answer is $y$ , your output is accepted if and only if $\frac{|x - y|}{\max(1, |y|)} \leq 10^{-9}$ .

C++ 解法, 执行用时: 330ms, 内存消耗: 10580K, 提交时间: 2021-11-22 11:47:06

#include <bits/stdc++.h>
using namespace std;

typedef long long s64;
s64 sqr(int x) {
	return s64(x) * x;
}
const double PI = acos(-1);
const int N = 1e5 + 5;
int x[N], r[N];
double la[N], ra[N];
int q[N], pos[N];
set<int> S;
double ans;
double area(int i) {
	if (la[i] <= ra[i]) return 0;
	return sqr(r[i]) * (la[i] - ra[i] + (sin(2 * ra[i]) - sin(2 * la[i])) / 2) / 2;
}
void check(int pl, int pr) {
	int d = x[pr] - x[pl];
	int r1 = r[pl], r2 = r[pr];
	if (d >= r1 + r2) return;
	ans -= area(pl) + area(pr);
	if (r2 >= r1 + d) {
		ra[pl] = PI;
	} else if (r1 >= r2 + d) {
		ra[pr] = PI;
	} else {
		double lx = (d + double(sqr(r1) - sqr(r2)) / d) / 2;
		ra[pl] = max(ra[pl], acos(lx / r1));
		la[pr] = min(la[pr], acos((-d + lx) / r2));
	}
	ans += area(pl) + area(pr);
}
void add(int i) {
	auto it = S.insert(pos[i]).first;
	la[i] = PI;
	ra[i] = 0;
	ans += area(i);
	while (it != S.begin()) {
		auto it0 = it;
		--it0;
		int pl = q[*it0];
		check(pl, i);
		if (la[i] <= ra[i]) return;
		if (la[pl] > ra[pl]) break;
		S.erase(it0);
	}
	while (1) {
		auto it1 = it;
		++it1;
		if (it1 == S.end()) break;
		int pr = q[*it1];
		check(i, pr);
		if (la[i] <= ra[i]) return;
		if (la[pr] > ra[pr]) break;
		S.erase(it1);
	}
}

int main() {
#ifdef kcz
	freopen("1.in", "r", stdin); //freopen("1.out","w",stdout);
#endif
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", x + i, r + i);
		q[i] = i;
	}
	sort(q + 1, q + n + 1, [&](int a, int b) { return x[a] < x[b]; });
	for (int i = 1; i <= n; ++i) pos[q[i]] = i;
	for (int i = 1; i <= n; ++i) {
		add(i);
		printf("%.9f\n", ans * 2);
	}
}

详情