hdu 1115(计算多边形重心)

时间:2024-05-23 18:36:08

题意:已知一多边形没有边相交,质量分布均匀。顺序给出多边形的顶点坐标,求其重心。

分析:

求多边形重心的题目大致有这么几种:

1,质量集中在顶点上。n个顶点坐标为(xi,yi),质量为mi,则重心
  X = ∑( xi×mi ) / ∑mi
  Y = ∑( yi×mi ) / ∑mi
  特殊地,若每个点的质量相同,则
  X = ∑xi / n
  Y = ∑yi / n

2,质量分布均匀。这个题就是这一类型,算法和上面的不同。
  特殊地,质量均匀的三角形重心:
  X = ( x0 + x1 + x2 ) / 3
  Y = ( y0 + y1 + y2 ) / 3

3,质量分布不均匀。只能用积分来算,不会……

2.7.2 猜想n边形的重心

猜想由n个点(x1,y1), (x2,y2), ……, (xn,yn)

构成的多边形的重心的坐标是:( ( x1+x2...+xn )/n,( y1+y2+...+yn )/n );

v上面公式失效的原因是面积代表的重量并不均匀分布在各个顶点上(如果重量均匀分布在各个顶点上,则上面公式成立)
v可以先求出各个三角形的重心和面积,然后对它们按照权重相加;
代码实现:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define esp 1e-7 using namespace std; struct Point{
double x,y;
Point(){}
Point(double x, double y):x(x),y(y){}
void input()
{
scanf("%lf%lf",&x,&y);
}
}; typedef Point Vector; Vector operator-(Vector A, Vector B)
{
return Vector(A.x-B.x, A.y-B.y);
} double Cross(Vector A, Vector B)
{
return A.x*B.y-A.y*B.x;
} double Area(Point A,Point B,Point C)
{
return Cross(B-A, C-A)/2.0;
} Point calZhongXing(Point *p, int n)//计算多边形重心
{
Point G;
int i;
double s,sumS=;
G.x=;G.y=;
for(i=;i<n-;i++)
{
s=Area(p[], p[i], p[i+]);
sumS+=s;
G.x+=(p[].x+p[i].x+p[i+].x)*s;
G.y+=(p[].y+p[i].y+p[i+].y)*s;
}
G.x=G.x/sumS/3.0;
G.y=G.y/sumS/3.0; return G;
} Point a[]; int main()
{
int T,i,n;
Point G;
scanf("%d",&T);
while(T--)
{ scanf("%d",&n);
for(i=;i<n;i++)
a[i].input();
G=calZhongXing(a, n);
printf("%.2lf %.2lf\n",G.x,G.y);
}
return ;
}