多角形 \(P\) の符号付き面積を \(\operatorname{area}(P)\)、幾何中心を \(g(P)\)、\(3\) 点 \(A,B,C\) を頂点とする三角形を \(\triangle ABC\) と書くことにします。

三角形 \(T\) の頂点が \((x_1,y_1),(x_2,y_2),(x_3,y_3)\) であるとき、以下が成り立ちます。

\[ g(T)=\left(\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3}\right) \]

元の問題の解法を考えます。 頂点 \(i\) を \(P_i\) とも書くこととし、任意の \(i\) に対して \(P_i=P_{i+N}\) が成り立つものとすると、\(2 \leq r-l \leq N-2\) を満たす整数 \(l,r\) について \(P_l,P_{l+1},\dots,P_r\) からなる多角形の幾何中心が求められればよいです。

多角形 \(P\) に対し \(m(P)=\operatorname{area}(P)g(P)\) とします（1次モーメント）。\(m\) は \(\operatorname{area}\) と同様の加法性をもちます。

解法1

原点 \(O\) を基準に考えると、頂点 \(l,l+1,\dots,r\ (2\leq r-l\leq N-2)\) からなる多角形 \(P'\) について

\[ \operatorname{area}(P') =\sum_{i=l}^{r-1}\operatorname{area}(\triangle OP_iP_{i+1}) +\operatorname{area}(\triangle OP_rP_l),\\ m(P')= \sum_{i=l}^{r-1}m(\triangle OP_iP_{i+1}) +m(\triangle OP_rP_l) \]

が成り立つため、\(P'\) の幾何中心は

\[ \frac{m(P')}{\operatorname{area}(P')}= \frac{ \sum_{i=l}^{r-1}m(\triangle OP_iP_{i+1}) +m(\triangle OP_rP_l) }{ \sum_{i=l}^{r-1}\operatorname{area}(\triangle OP_iP_{i+1}) +\operatorname{area}(\triangle OP_rP_l) } \]

と表せます（面積は符号付きであることに注意）。 これは \(\operatorname{area}(\triangle OP_iP_{i+1})\) と \(m(\triangle OP_iP_{i+1})\)（の \(x,y\) 成分それぞれ）の累積和をそれぞれ前計算しておけば \(O(1)\) 時間で求めることができ、元の問題は全体で \(O(N+Q)\) 時間で解くことができます。

ただし浮動小数点型によって累積和を計算すると、桁落ちにより WA になることがあるので注意が必要です。

今回の制約下では \(\operatorname{area}(\cdot)\) を \(2\) 倍、\(m(\cdot)\) を \(6\) 倍することでどちらも整数になります。 さらに、上の方法で現れる累積和を含めてすべての値を 64 bit 整数型の範囲で計算できることが証明できます（付録参照）。

実装例では整数型で累積和を計算し、最後に浮動小数点型で割り算をしています。

実装例(C++) / 実装例(Python)

解法2

頂点 \(l,l+1,\dots,r\) からなる多角形を \(S_{l,r}\) とします。

頂点 \(l,c,r\) が反時計回り順に並んでいるとき、\(S_{l,r}\) は内部が重ならないように \(S_{l,c},S_{c,r},\triangle P_lP_cP_r\) に分割できます。

特に \(\operatorname{area}(S_{l,r}),m(S_{l,r})\) はそれぞれ \(S_{l,c},S_{c,r},\triangle P_lP_cP_r\) についての \(\operatorname{area},m\) の値の総和と等しいです。

従って区間 \([l,r)\) に \(S_{l,r}\) を対応付けて \(P_l,P_r\) の座標および \(\operatorname{area}\) と \(m\) の値を持ち、セグメント木を利用すれば全体で \(O(N+Q\log N)\) 時間で解くことができます。

実装例(C++)

---

付録：解法 1 が 64 bit 整数型で計算できることの説明

\(2\leq r-l \leq N-2\) のときに \(2\sum_{i=l}^{r-1}\operatorname{area}(\triangle OP_iP_{i+1})\) と \(6\sum_{i=l}^{r-1}m(\triangle OP_iP_{i+1})\) が符号付き 64 bit 整数型の範囲に収まることを説明します。

\(P\) の頂点の座標がすべて \(-R\) 以上 \(R\) 以下であるとします。今回の制約下では \(R=5\times 10^5\) です。

まず \(\operatorname{area}\) について考えます。 \(P\) は凸多角形より \(\sum_{i=l}^{r-1}|x_{i+1}-x_i|\leq 4R\) および \(\sum_{i=l}^{r-1}|y_{i+1}-y_i|\leq 4R\) であることを用いれば、以下が成り立ちます。

\[\begin{aligned} \left|2\sum_{i=l}^{r-1}\operatorname{area}(\triangle OP_iP_{i+1})\right| &=\left|\sum_{i=l}^{r-1}(x_iy_{i+1}-y_ix_{i+1})\right|\\ &=\left|\sum_{i=l}^{r-1}\left(x_i(y_{i+1}-y_i)-y_i(x_{i+1}-x_i)\right)\right|\\ &\leq\sum_{i=l}^{r-1}\left(|x_i|\cdot|y_{i+1}-y_i|+|y_i|\cdot|x_{i+1}-x_i|\right)\\ &\leq\sum_{i=l}^{r-1}\left(R\cdot|y_{i+1}-y_i|+R\cdot|x_{i+1}-x_i|\right)\\ &\leq 8R^2=2\times 10^{12} \end{aligned}\]

次に \(m\) について考えます。 \(m\) の \(x\) 成分を \(m_x\) としたとき

\[\begin{aligned} \left|6\sum_{i=l}^{r-1}m_x(\triangle OP_iP_{i+1})\right| &=\left|\sum_{i=l}^{r-1}(x_i+x_{i+1})(x_iy_{i+1}-y_ix_{i+1})\right|\\ &=\left|\sum_{i=l}^{r-1}\left((x_i^2+x_ix_{i+1}+x_{i+1}^2)(y_{i+1}-y_i)+x_i^2y_i-x_{i+1}^2y_{i+1}\right)\right|\\ &=\left|\sum_{i=l}^{r-1}(x_i^2+x_ix_{i+1}+x_{i+1}^2)(y_{i+1}-y_i)+x_l^2y_l-x_r^2y_r\right|\\ &\leq\left|\sum_{i=l}^{r-1}(x_i^2+x_ix_{i+1}+x_{i+1}^2)(y_{i+1}-y_i)\right|+|x_l^2y_l|+|x_r^2y_r|\\ \end{aligned}\]

が成り立ちます。 ここで \(0 \leq x_i^2+x_ix_{i+1}+x_{i+1}^2 \leq 3R^2\)、また \(P\) は凸より \(\sum_{i=l}^{r-1}\min(0,y_{i+1}-y_i)\geq -2R,\sum_{i=l}^{r-1}\max(0,y_{i+1}-y_i)\leq 2R\) であることから

\[\begin{aligned} \left|6\sum_{i=l}^{r-1}m_x(\triangle OP_iP_{i+1})\right| &\leq\left|\sum_{i=l}^{r-1}(x_i^2+x_ix_{i+1}+x_{i+1}^2)(y_{i+1}-y_i)\right|+|x_l^2y_l|+|x_r^2y_r|\\ &\leq6R^3+R^3+R^3\\ &\leq8R^3=10^{18} \end{aligned}\]

が得られます。\(y\) 成分についても同様です。

• \(m\) の区間和の絶対値はより強く \(6R^3\) 以下であることが示せます。基準点を原点でなく \(P_1\) などにした解法だと示しやすいです。
• 累積和を二周分持つ解法も今回の制約下では正当ですが、\(R=10^6\) などもっと制約が大きい場合は累積和が 64 bit 整数型ではオーバーフローし、未定義動作となる可能性があります。