AT_abc472_f [ABC472F] Centroid of a Slice

在 $xy$ 平面上有一个凸 $N$ 边形 $P$。$P$ 的顶点按照逆时针方向编号为 $1,2,\dots,N$，第 $i$ 个顶点的坐标为 $(x_i, y_i)$。 你需要回答 $Q$ 个问题。 对于第 $j$ 个问题，会给出两个不同的顶点 $u_j$ 和 $v_j$。这里，$u_j$ 和 $v_j$ 在 $P$ 的边界上不是相邻的顶点。 连接顶点 $u_j$ 和 $v_j$ 的线段会将 $P$ 分成两个多边形；记 $P'$ 为从顶点 $u_j$ 指向顶点 $v_j$ 的有向直线右侧的那个多边形。请你求出 $P'$ 的几何中心坐标（即把多边形内部看作均匀薄板时的质心坐标）。

输入从标准输入读入，格式如下： > $N$ $Q$ > $x_1$ $y_1$ > $x_2$ $y_2$ > $\vdots$ > $x_N$ $y_N$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_Q$ $v_Q$

输出 $Q$ 行。第 $j$ 行，设答案为坐标 $(p_j, q_j)$，请按 $p_j$ 和 $q_j$ 的顺序输出，两个数之间用一个空格隔开。 对于每个 $p_j$ 和 $q_j$，其与真值的绝对误差或相对误差不超过 $10^{-6}$ 时，答案即被认为是正确的。

### 样例解释 1 对于第一个问题，$P'$ 为顶点 $(1,3),(-3,2),(-1,-2)$ 构成的三角形，其几何中心为 $(-1,1)$。 对于第二个问题，$P'$ 为顶点 $(2,-1),(4,1),(1,3),(-3,2)$ 构成的四边形，其几何中心为 $\left(\frac{70}{81},\frac{98}{81}\right)$。 ### 数据范围 - $4 \leq N \leq 3 \times 10^4$ - $1 \leq Q \leq 2 \times 10^5$ - $|x_i|, |y_i| \leq 5 \times 10^5$ - $(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)$ 构成一个逆时针有序的凸多边形。 - $P$ 的每个内角都小于 $180$ 度。 - $1 \leq u_j, v_j \leq N$ - $u_j \neq v_j$ - $u_j$ 和 $v_j$ 在 $P$ 的边界上不相邻。 - 所有输入数值均为整数。 由 ChatGPT 5 翻译