P1385. 抬起石头

题目描述

地面上有许多被巨大沉重石头覆盖的秘密开口。当石头被抬起时，特殊机制会检测到这一动作并激活附近的毒箭发射装置。唯一的办法是缓慢而小心地抬起石头。ACM团队必须将绳子系在石头上，然后使用滑轮抬起。而且，石头必须一次性整体抬起，任何一边都不能先于其他边抬起。因此，找到重心并将绳子精确连接到该点至关重要。石头呈多边形形状，且整个多边形区域的高度均匀。你的任务是找到给定多边形的重心位置。

输入格式

输入包含$T$个测试用例。第一行给出测试用例的数量$T$。每个测试用例包含：

• 第一行：一个整数$N$（$3 \leq N \leq 1000000$），表示构成多边形的点数
• 接下来$N$行：每行两个整数$X_i$和$Y_i$（$|X_i|, |Y_i| \leq 20000$），表示第$i$个点的坐标

按给定顺序连接这些点将形成一个多边形。可以假设多边形的边除相邻边外不会相互接触，也不会交叉。多边形面积永远不会为零（即不会退化成一条直线）。

输出格式

每个测试用例输出一行，包含两个用空格分隔的数字，表示重心的坐标。坐标四舍五入到小数点后两位（0.005将进位为0.01）。注意重心可能位于多边形外部（如果形状非凸），出现这种情况时仍应输出计算得到的重心位置。

示例输入

2
4
5 0
0 5
-5 0
0 -5
4
1 1
11 1
11 11
1 11

示例输出

0.00 0.00
6.00 6.00

来源

Central Europe 1999

数学原理

多边形重心计算公式：

$$C_x = \frac{1}{6A}\sum_{i=0}^{n-1}(x_i + x_{i+1})(x_i y_{i+1} - x_{i+1} y_i) $$$$C_y = \frac{1}{6A}\sum_{i=0}^{n-1}(y_i + y_{i+1})(x_i y_{i+1} - x_{i+1} y_i) $$

其中$A$为多边形有向面积：

$$A = \frac{1}{2}\sum_{i=0}^{n-1}(x_i y_{i+1} - x_{i+1} y_i) $$

注意：当$i=n-1$时，$x_{i+1}=x_0$，$y_{i+1}=y_0$