题目描述

$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}$ 即视为正确。

数据范围

• $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$ 的边界上不相邻。
• 输入中的所有值均为整数。

5 4
4 1
1 3
-3 2
-1 -2
2 -1
2 4
5 3
1 4
4 2

-1.000000000000000 1.000000000000000
0.864197530864198 1.209876543209877
0.198198198198198 0.828828828828829
1.391304347826087 0.434782608695652

对于第一个询问，$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)$。

10 10
480451 142016
404696 274257
7097 390813
-134582 195390
-167108 143104
-359470 -180367
-406293 -273476
74335 -494832
486873 -391664
493159 -292349
5 8
8 6
5 2
5 1
10 3
1 7
3 5
2 5
4 9
1 8

-167917.431926206833203 -207268.968943785114349
126221.026579795702381 -68771.715180365014040
111801.954824466955586 -124063.178438661167072
99590.935535112756283 -153792.378227918737825
321662.353363423237819 113722.100435559268610
43574.061369374611386 102411.022160871806300
-98197.666666666666667 243102.333333333333333
79984.488622522356481 269160.678085376751920
-3267.792578363696043 -210454.379232334372417
46257.363593155145794 -38546.483790939251583

• 来源：AtCoder ABC 472 F

子任务设置

• 子任务 1（$30\%$）：$N,Q \le 2000$。
• 子任务 2（$30\%$）：$N \le 2000$，$Q \le 5 \times 10^4$。
• 子任务 3（$40\%$）：无特殊限制。