ABC472 F - Centroid of a Slice

切断部の重心

考え方

物理学の重心の問題。
公式としては、以下のようになる。
ただし、$\rho$ は面密度。

$$
g_x = \dfrac{\iint \rho x \ \mathrm{d}x\mathrm{d}y}{\iint \rho \ \mathrm{d}x\mathrm{d}y}, g_y = \dfrac{\iint \rho y \ \mathrm{d}x\mathrm{d}y}{\iint \rho \ \mathrm{d}x\mathrm{d}y}
$$

とはいえ、さすがに積分の計算などやっていられないので、うまく対応することを考える。

この値は、領域が三角形で密度 $\rho$ が一定だった場合、分子分母それぞれ簡単に計算できる。
すなわち、$\triangle\mathrm{ABC}$ の符号付き面積を $S$ とすると、以下のようになる。

$$
\begin{aligned}
\text{分母} &= \rho S = \rho\overrightarrow{\mathrm{AB}}\times\overrightarrow{\mathrm{AC}}/2 \\
g_x\text{ の分子} &= (\mathrm{A}_x+\mathrm{B}_x+\mathrm{C}_x)\rho S/3 \\
g_y\text{ の分子} &= (\mathrm{A}_y+\mathrm{B}_y+\mathrm{C}_y)\rho S/3
\end{aligned}
$$

さらに、複数の物体の合体の場合、この積分値を分子分母それぞれ（約分せずに）足した値にすればよい。
切り落としの場合は同様に引けばよい。
ということは、多角形を大量の三角形に分割し、上記の公式と合体による総和で積分は回避可能。

0-indexed で、$\mathrm{P}$ の $i$ 番目の頂点を $\mathrm{A}_i$ と書くことにする。
$i=1,2,\dots,N-1$ に対し、$\triangle\mathrm{A}_{N-1}\mathrm{A}_{i-1}\mathrm{A}_i$ を求めておく。
（$i=N-1$ の場合は明らかに $0$ だが）

まず、$u<v$ である場合。（これらも 0-indexed に直してあるとする）
この場合、まず $\triangle\mathrm{A}_{N-1}\mathrm{A}_{u}\mathrm{A}_{u+1},\triangle\mathrm{A}_{N-1}\mathrm{A}_{u+1}\mathrm{A}_{u+2},\dots\triangle\mathrm{A}_{N-1}\mathrm{A}_{v-1}\mathrm{A}_{v}$ を合体する。
そこにさらに $\triangle\mathrm{A}_{N-1}\mathrm{A}_{v}\mathrm{A}_{u}$ を合体すればよい。
最後の三角形は符号付き面積が負（または $0$）になるため、実質引き算である。
これを用いて分子と分母をそれぞれ計算し、割り算をすればよい。

$u>v$ である場合は、同じ計算をすると、扱いたい図形の逆側が負符号で出てくる。
よって、そこに図形全体の値を加算することで、意図した値となる。

……というのを累積和で処理することによって、$O(N)$ の事前処理のもと、各クエリが $O(1)$ で解ける。
よって、計算量は $O(N+Q)$ となる。

なお、小数を扱うのは望ましくないため、分母は $2$ 倍、分子は $6$ 倍した値で扱うとよい。
すべて整数で扱え、しかも long long 型の範囲から溢れることも起こらない。
また、$\rho$ の値はどうせ最終的に約分で消えるだけの値なので、$1$ としてしまってよい。

入力例1での動作

入力を受け取る。

n: 5
q: 4
p:
(4, 1)
(1, 3)
(-3, 2)
(-1, -2)
(2, -1)
queries:
(2, 4)
(5, 3)
(1, 4)
(4, 2)

頂点は 0-indexed で $\mathrm{A}_0=(4,1)$, $\mathrm{A}_1=(1,3)$, $\mathrm{A}_2=(-3,2)$, $\mathrm{A}_3=(-1,-2)$, $\mathrm{A}_4=(2,-1)$ である。

$\mathrm{A}_4$ を基準に、$\triangle\mathrm{A}_4\mathrm{A}_{i-1}\mathrm{A}_i$ を順に足していく。
各三角形について、分母の $2$ 倍と、$g_x,g_y$ の分子の $6$ 倍を求め、それぞれ累積和を取る。
$g_x,g_y$ の分子の $6$ 倍は、以下では $(x,y)$ の組で表す。

$i$	分母の $2$ 倍	分子の $6$ 倍 $(x,y)$	分母の $2$ 倍の累積	分子の $6$ 倍の累積 $(x,y)$
$1$	$10$	$(70,30)$	$10$	$(70,30)$
$2$	$17$	$(0,68)$	$27$	$(70,98)$
$3$	$14$	$(-28,-14)$	$41$	$(42,84)$
$4$	$0$	$(0,0)$	$41$	$(42,84)$

まず、最初のクエリ 2 4 を考える。
0-indexed では $u=1,v=3$ である。
累積和の差を取ると、$\triangle\mathrm{A}_4\mathrm{A}_1\mathrm{A}_2$ と $\triangle\mathrm{A}_4\mathrm{A}_2\mathrm{A}_3$ の合計が求まる。
この時点では、分母の $2$ 倍は $17+14=31$、分子の $6$ 倍は $(0,68)+(-28,-14)=(-28,54)$ である。

さらに $\triangle\mathrm{A}_4\mathrm{A}_3\mathrm{A}_1$ を加える。
この三角形の符号付きの分母の $2$ 倍は $-13$、分子の $6$ 倍は $(-26,0)$ なので、以下のようになる。

分母の $2$ 倍が $31-13=18$
分子の $6$ 倍が $(-28,54)+(-26,0)=(-54,54)$

したがって重心は $(-54,54)/(3\times18)=(-1,1)$ である。

次に、$2$ つめのクエリ 5 3 を考える。
0-indexed では $u=4,v=2$ で、$u>v$ となる。
先ほどと同じように累積和の差を取り、両端を直接つなぐ三角形も加える。
このクエリでは $u=4$、つまり $\mathrm{A}_u=\mathrm{A}_4$ が基準点そのものなので、補正用の三角形は面積 $0$ である。
その結果、分母の $2$ 倍は $-14$、分子の $6$ 倍は $(28,14)$ となる。
これは求めたい領域ではなく、その逆側の領域を負符号で求めた値である。

そこで、多角形全体の値である、分母の $2$ 倍 $41$、分子の $6$ 倍 $(42,84)$ を加える。
すると、以下のようになる。

分母の $2$ 倍が $-14+41=27$
分子の $6$ 倍が $(28,14)+(42,84)=(70,98)$

したがって重心は $(70,98)/(3\times27)=(70/81,98/81)$ であり、これが入力例1の $2$ つめの答えである。

注意点

三角形の符号付き面積の $2$ 倍や、それに座標を掛けて累積する値は、int 型からはみ出る場合がある。
long long 型を用いること。

別解

特になし。