For a polygon \(P\), denote its signed area by \(\operatorname{area}(P)\), its geometric center by \(g(P)\). Write a triangle with vertices \(A,B,C\) as \(\triangle ABC\).

A triangle \(T\) with vertices \((x_1,y_1),(x_2,y_2),(x_3,y_3)\) satisfies:

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

We will consider the original problem. Denote vertex \(i\) also by \(P_i\), and assume that \(P_i=P_{i+N}\) for all \(i\). Then it is sufficient to find the geometric center of the polygon formed by \(P_l,P_{l+1},\dots,P_r\).

For a polygon \(P\), let \(m(P)=\operatorname{area}(P)g(P)\) (called first moment). \(m\) is additive in the same manner as \(\operatorname{area}\).

Solution 1

Taking the origin \(O\) as the pivot, the polygon \(P'\) formed by \(l,l+1,\dots,r\ (2\leq r-l\leq N-2)\) satisfies:

\[ \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), \]

so the geometric center of \(P'\) is

\[ \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). } \]

(Note that the areas are signed.) This can be computed in \(O(1)\) time by precalculating the cumulative sums of \(\operatorname{area}(\triangle OP_iP_{i+1})\) and \(m(\triangle OP_iP_{i+1})\) (for each of \(x\) and \(y\) component), so the original problem can be solved in a total of \(O(N+Q)\) time.

Note that computing cumulative sums using floating-point number type may cause a cancellation, leading to WA (Wrong Answer).

Under the constraints of the problem, \(2\) times \(\operatorname{area}(\cdot)\) and \(6\) times \(m(\cdot)\) are both integers. Moreover, one can prove that all intermediate values, including the cumulative sums required in the expression above, fit in the 64-bit integer type (see the Appendix).

In the sample code, we compute the cumulative sums using an integer type, and finally perform division as floating-point type values.

Sample code (C++) / Sample code (Python)

Solution 2

Let \(S_{l,r}\) be the polygon formed by vertices \(l,l+1,\dots,r\).

When vertices \(l,c,r\) are arranged counterclockwise, \(S_{l,r}\) can be divided into \(S_{l,c}\), and \(S_{c,r}\), and \(\triangle P_lP_cP_r\), so that their interiors do not overlap.

In particular, \(\operatorname{area}(S_{l,r})\) and \(m(S_{l,r})\) are equal to the sum of \(\operatorname{area}\) and \(m\), respectively, of \(S_{l,c}\), and \(S_{c,r}\), and \(\triangle P_lP_cP_r\).

Therefore, the problem can be solved in a total of \(O(N+Q\log N)\) time using a segment tree, by identifying node \([l,r)\) with \(S_{l,r}\) and storing the coordinates of \(P_l\) and \(P_r\) and the values of \(\operatorname{area}\) and \(m\).

Sample code (C++)

---

Appendix: proof that solution 1 can be implemented using 64-bit integer type

We will prove that \(2\sum_{i=l}^{r-1}\operatorname{area}(\triangle OP_iP_{i+1})\) and \(6\sum_{i=l}^{r-1}m(\triangle OP_iP_{i+1})\) fits within the range of the 64-bit integer type.

Assume that the coordinates of the vertices of \(P\) are all within \(-R\) to \(R\). In our constraints, \(R=5\times 10^5\).

First, consider \(\operatorname{area}\). Since \(P\) is a convex polygon, \(\sum_{i=l}^{r-1}|x_{i+1}-x_i|\leq 4R\) and \(\sum_{i=l}^{r-1}|y_{i+1}-y_i|\leq 4R\), so:

\[\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}\]

Next, consider \(m\). Writing the \(x\)-coordinate of \(m\) by \(m_x\), one has

\[\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}\]

Here, \(0 \leq x_i^2+x_ix_{i+1}+x_{i+1}^2 \leq 3R^2\), and \(\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\) by the convexity of \(P\), we obtain

\[\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}\]

Same goes for \(y\) coordinates.

• More strongly, the absolute value of the segment sum of \(m\) is at most \(6R^3\). Taking \(P_1\) as the pivot instead of the origin makes it easier to proof.
• Solutions using cumulative sums for two cycles are also valid under the constraints of this problem, but if they were even larger, say \(R=10^6\), 64-bit integer type would overflow, potentially triggering an undefined behavior.