AT_abc472_f.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$ 行中，设第 $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^\circ$。
• $1 \leq u_j,v_j \leq N$
• $u_j \neq v_j$
• 顶点 $u_j$ 和 $v_j$ 在 $P$ 的边界上不相邻。
• 所有输入值均为整数。