NYOJ 题目3 多边形重心

本文主要是介绍NYOJ 题目3 多边形重心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

多边形重心问题

描述

在某个多边形上，取n个点，这n个点顺序给出，按照给出顺序将相邻的点用直线连接， （第一个和最后一个连接），所有线段不和其他线段相交，但是可以重合，可得到一个多边形或一条线段或一个多边形和一个线段的连接后的图形；
如果是一条线段,我们定义面积为0，重心坐标为（0,0）.现在求给出的点集组成的图形的面积和重心横纵坐标的和；

输入

第一行有一个整数0<n<11,表示有n组数据；
每组数据第一行有一个整数m<10000,表示有这个多边形有m个顶点；

输出

输出每个多边形的面积、重心横纵坐标的和，小数点后保留三位；

样例输入

3
3
0 1
0 2
0 3
3
1 1
0 0
0 1
4
1 1
0 0
0 0.5
0 1

样例输出

0.000 0.000
0.500 1.000
0.500 1.000

 

关于多边形的面积 有一个化简的公式：看这里 计算多边形面积

 

 

计算重心：

1.将各个点存入数组；（数组最后增加一个 点 等于第一个 点，为了首尾相接）

2. 以原点为定点，计算每个三角形的（有向）面积和，总面积就是 对和取绝对值，

3. 计算出每个三角形的（加权）重心， X = S *(x1+x2+0)/3;    Y = S *（y1+y2+0）/3;

4. 然后多边形的重心坐标为  Gx = X总 / S总;  Gy = Y总 / S总;

 

#include <stdio.h>
#include <math.h>
struct point{
double x,y;
}; point p[10004];
int main()
{
int n,m,i;
scanf("%d",&n);
while(n--){
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
p[m] = p[0]; //注意最后一个点与第一个点的相连 
double x,y,s,temp;
x = y = s = 0;
for(i=0;i<m;i++){
temp = (p[i].x*p[i+1].y-p[i].y*p[i+1].x)/2;//有向面积
s += temp;//总有向面积
x += temp * (p[i].x+p[i+1].x)/3; //加权 
y += temp * (p[i].y+p[i+1].y)/3;  
}
if(fabs(s)<0.0000001) printf("0.000 0.000\n"); //面积为0
else printf("%.3lf %.3lf\n",fabs(s),(x+y)/s); 
}
return 0; 
} 

 

 

这篇关于NYOJ 题目3 多边形重心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---