首页 > 代码库 > hdu 1115（计算多边形重心）

hdu 1115（计算多边形重心）

2024-07-19 15:53:13   225人阅读

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

分析：

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

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-7using 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=0;    G.x=0;G.y=0;    for(i=1;i<n-1;i++)    {        s=Area(p[0], p[i], p[i+1]);        sumS+=s;        G.x+=(p[0].x+p[i].x+p[i+1].x)*s;        G.y+=(p[0].y+p[i].y+p[i+1].y)*s;    }    G.x=G.x/sumS/3.0;    G.y=G.y/sumS/3.0;    return G;}Point a[1000005];int main(){    int T,i,n;    Point G;    scanf("%d",&T);    while(T--)    {                scanf("%d",&n);        for(i=0;i<n;i++)            a[i].input();        G=calZhongXing(a, n);        printf("%.2lf %.2lf\n",G.x,G.y);    }    return 0;}

 

hdu 1115（计算多边形重心）


联系
我们