A7723 · 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

输出 #1

-1.000000000000000 1.000000000000000
0.864197530864198 1.209876543209877
0.198198198198198 0.828828828828829
1.391304347826087 0.434782608695652

输入 #2

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

输出 #2

-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

A7723 | Centroid of a Slice

题目描述

输入格式

输出格式

输入输出样例

A7723 | $Centroid of a Slice$