HDOJ（1115）多边形重心

时间：2023-03-08 15:47:22
HDOJ（1115）多边形重心

Lifting the Stone

http://acm.hdu.edu.cn/showproblem.php?pid=1115

题目描述：输入n个顶点（整数）,求它们围成的多边形的重心。

算法：以一个点出发，与其他非邻点相连，将n边形划分成n-2个三角形。求每个三角形的质点系重心（如：((x1+x2+x3)/3,(y1+y2+y3)/3)），再求出每个三角形的面积。相乘求和后除以多边形面积）。

注意：we connect the points in the given order。输入的顺序，要么是顺时针，要么是逆时针。

#include <iostream>

#include <iomanip>

#include <vector>

using namespace std;

struct Node  //顶点或向量结构

{

    int x;

    int y;

};

vector<Node> node;

int main()

{

    int t,n;

    double cross_sum,x_sum,y_sum;

    cin>>t;

    while(t--)

    {

        node.clear();

        cross_sum=;

        x_sum=y_sum=;

        cin>>n;

        for(int i=;i<=n;i++)

        {

            Node temp;  //顶点

            cin>>temp.x>>temp.y;

            node.push_back(temp);

        }

        Node vec1,vec2; //向量

        vec1.x=node[].x-node[].x;

        vec1.y=node[].y-node[].y;

        for(int i=;i<=n-;i++)

        {

            vec2.x=node[i].x-node[].x;

            vec2.y=node[i].y-node[].y;

            int cross=vec1.x*vec2.y-vec2.x*vec1.y;

            x_sum+=(double)(node[].x+node[i-].x+node[i].x)*cross;

            y_sum+=(double)(node[].y+node[i-].y+node[i].y)*cross;

            cross_sum+=cross;

            vec1=vec2;

        }

        double res_x=x_sum/(*cross_sum);

        double res_y=y_sum/(*cross_sum);  //最后用除法，且少用除法，减少精度丢失

        cout<<fixed<<setprecision()<<res_x<<" "<<res_y<<endl;

    }

    return ;

}

做了几道计算几何的题目，不得不说向量是个好东西！！！是哪位神人发明的向量，膜拜。

下面是别人写的的求多边形重心的方法：

线垂法：

　　具体方法是：用细线提起该物体，在该物体上画细线的延长线，再移位用细线提起该物体，在该物体上画细线的延长线，两线的交叉点就是这一物体在这平面上的重心，　　　　　　　　其它面同理．适用于实际测量中。

定理法：(本人自己命名)
　　定理1： 由两个图形A，B合并而成的一个图形C，则C的重心必在A的重心与B的重心连接的线段上。(注意，也适用于A B彼此分开，没有公共点的情形)
　　定理2： 由两个A，B合并而成的一个图形C，A的重心为点a, B的重心为点b, C的重心为点c, A的面积为Sa, B的面积为Sb,则下面条件成立：
　　　　　　(1)点c 必在线段 ab 上
　　　　　　(2) ac * Sa = bc * Sb

计算几何中：
　　　　三角形的重心： x = (xa+xb+xc)/3,  y = (ya+yb+yc)/3;
　　　　四边形的重心：作一对角线，将它分成两个三角形分别求出重心与面积 (x1,y1) ,s1 ; (x2, y2), s2 则该四边形的重心为： x = (x1*s1+x2*s2)/(s1+s2), y = (y1*s1+y2*s2)/(s1+s2);
　　　　五边形则分为一个三角形与一个四边形……

　　　　任意多边形中直接取任一点（一般为原点）把多边形分为n-2个三角形 分别求重心
　　　　　　x=∑ si * xi / ∑si
　　　　　　y=∑ si * yi / ∑si
　　　　　　si 为每块三角形的有向面积 (就是向量叉积/2)

相关文章