题解 P17221【[ICPC 2017 Nanning R] Resonators】

· · 题解

Resonators

\color{gold}{\textsf{Medium-Hard}}

给出平面上 n 个圆 C_i，记这些圆的并集区域为 \Omega:= \bigcup_{i=1}^{n} C_i，求 \displaystyle\iint_{\Omega}(x^2+y^2)\,dxdy。

1\leq n\leq 1000.

套用格林公式

\iint_\Omega(x^2+y^2)\,dxdy=\frac14\oint_C(x^2+y^2)(xdy-ydx)

将圆弧参数化，单段圆弧贡献为

x=x_0+r\cos t,\ y=y_0+r\sin t,\\ \frac r4\int_\alpha^\beta \bigl(x_0^2+y_0^2+r^2+2r(x_0\cos t+y_0\sin t)\bigr) \bigl(r+x_0\cos t+y_0\sin t\bigr)\,dt

其原函数可用

\begin{aligned} F(t)&=\frac r4\Big[(2r(x_0^2+y_0^2)+r^3)t\\ &+\frac r2(x_0^2-y_0^2)\sin 2t\\ &-rx_0y_0\cos 2t\\ &+(x_0^3+x_0y_0^2+3x_0r^2)\sin t\\ &-(x_0^2y_0+y_0^3+3y_0r^2)\cos t \Big] \end{aligned}

所以答案就是各段求和

\sum_{\text{arc}}\bigl(F(\beta)-F(\alpha)\bigr)

朴素时间复杂度 \mathcal{O}(n^2)，容易做到 \mathcal{O}(n\log n)。