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)