POJ 1385 Lifting the Stone（计算几何，多边形重心）

计算几何，多边形重心
本题要点：
1、三角形重心，很容易，就是 3个点的x坐标，y坐标的平均值。
2、多边形的重心，可以看做是，其分解成 n - 2 个三角形，每个三角形重心的加权平均值。
3、 n 开到 1e5 就可以 AC了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
double eps = 1e-8;
const int MaxN = 1e5 + 10;
int T, n;int sgn(double x)
{
    if(fabs(x) < eps)return 0;elsereturn x < 0 ? -1 : 1;
}struct Point
{
    double x, y;Point(double X = 0, double Y = 0)	{
    x = X, y = Y;}Point operator + (Point B)	{
    return Point(x + B.x, y + B.y);}Point operator - (Point B)	{
    return Point(x - B.x, y - B.y);}Point operator * (double k)	{
    return Point(x * k, y * k);}Point operator / (double k)	{
    return Point(x / k, y / k);}
};Point p[MaxN], center;typedef Point Vector;double Cross(Vector A, Vector B)	// 叉积
{
    return A.x * B.y - A.y * B.x;
}double Poly_area(Point *p, int n)	// 计算多边形的面积
{
    double area = 0;for(int i = 0; i < n; ++i){
    area += Cross(p[i], p[(i + 1) % n]);}return area / 2;
}Point Poly_center(Point *p, int n)	// 求多边形的重心
{
    Point ans(0, 0);if(sgn(Poly_area(p, n)) == 0)return ans;for(int i = 0; i < n; ++i){
    ans = ans + (p[i] + p[(i + 1) % n]) * Cross(p[i], p[(i + 1) % n]);}return ans / Poly_area(p, n) / 6;
}int main()
{
    scanf("%d", &T);while(T--){
    scanf("%d", &n);for(int i = 0; i < n; ++i){
    scanf("%lf%lf", &p[i].x, &p[i].y);}center = Poly_center(p, n);printf("%.2f %.2f\n", center.x, center.y);}return 0;
}/* 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 */