HDUOJ1115-计算机几何计算入门

    题目链接：
    要求：计算一块多边形（凹、凸）几何重心
    方法：①将多边形分成（n-2）个三角形；
              ②分别求出（n-2）个三角形的（有向）面积和重心，既 S[i]、centre.x, centre.y，有向面积可保证凹多边形的正负面积相互抵消；
              ③求（n-2）个三角形的重心所组成的多边形的加权重心；
                
    AC要注意的几个地方：
            ①数据要用double类型；
            ②所有除法放到最后进行运算，减少精度损失。

#include<stdio.h>
#define N 1000008

struct _data
{
    double x;
    double y;

    double area;

    double centre_x;
    double centre_y;
};

struct _data coordinate[N];

double get_area(struct _data a, struct _data b, struct _data c)
{
    double _a_x = b.x - a.x;
    double _a_y = b.y - a.y;

    double _b_x = c.x - a.x;
    double _b_y = c.y - a.y;

    //此处本应是 (_a_x * _b_y - _b_x * _a_y) / 2，
    //但考虑到在后面的运算中 / 2 会被抵消，所以为减少精度损失，在此将其去掉
    return (_a_x * _b_y - _b_x * _a_y);
}

int main(void)
{
    int T;
    int n;
    struct _data centre;
    double all_area;

    scanf("%d", &T);
    while(T--)
    {
        centre.x = 0;
        centre.y = 0;

        all_area = 0;

        scanf("%d", &n);
        for(int i = 0; i < n; i++)
        {
            scanf("%lf%lf", &coordinate[i].x, &coordinate[i].y);
        }

        for(int i = 1; i < n - 1; i++)
        {
            coordinate[i].area = get_area(coordinate[0], coordinate[i], coordinate[i+1]);
            all_area += coordinate[i].area;

            coordinate[i].centre_x = (coordinate[0].x + coordinate[i].x + coordinate[i+1].x);
            coordinate[i].centre_y = (coordinate[0].y + coordinate[i].y + coordinate[i+1].y);
        }

        for(int i = 1; i < n - 1; i++)
        {
            centre.x += coordinate[i].centre_x * coordinate[i].area;
            centre.y += coordinate[i].centre_y * coordinate[i].area;
        }

        centre.x /= all_area * 3;
        centre.y /= all_area * 3;

        //四舍五入
        //centre.x = (int)((centre.x * 100) + 0.5) / 100.0;
        //centre.y = (int)((centre.y * 100) + 0.5) / 100.0;
        printf("%.2lf %.2lf\n", centre.x, centre.y);
    }

    return 0;
}