标题的含义：
给定一个n刚n顶点。这是获得n分众协调多边形。
pid=1115
题目分析：
/**
*出处：
*①质量集中在顶点上 * n个顶点坐标为(xi,yi)。质量为mi，则重心 * X = ∑( xi×mi ) / ∑mi * Y = ∑( yi×mi ) / ∑mi * 特殊地。若每一个点的质量同样。则 * X = ∑xi / n * Y = ∑yi / n *②质量分布均匀 * 特殊地。质量均匀的三角形重心： * X = ( x0 + x1 + x2 ) / 3 * Y = ( y0 + y1 + y2 ) / 3 *③三角形面积公式：S = ( (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) ) / 2 ; *做题步骤：1、将多边形切割成n-2个三角形。依据③公式求每一个三角形面积。 * 2、依据②求每一个三角形重心。 * 3、依据①求得多边形重心。 **/
如今根据此算法给出两种代码，一种是将n个点。以当中一个点为标准。分成n-2个三角形。再进行求重心。
还有一种是以原点为根据分成n+1个三角形，再进行求重心。
AC代码：
第一种代码：
#include<iostream> #include<cmath> #include<cstdio> using namespace std; struct Point{ double x,y; }; double Area(Point p1,Point p2,Point p3){//叉乘求三角形面积 return ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))/2; } int main() { int n,t; scanf("%d",&t); while(t--){ scanf("%d",&n); Point p1,p2,p3; double gx,gy,sumarea; gx=gy=sumarea=0; scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y); for(int i=2;i<n;i++){//分成n-2个三角形 scanf("%lf%lf",&p3.x,&p3.y); double area=Area(p1,p2,p3);//单个三角的面积 gx+=(p1.x+p2.x+p3.x)*area;//重心乘以其权值(面积),由于每个都要除以3,所医院放在最后 gy+=(p1.y+p2.y+p3.y)*area; sumarea+=area;//计算全部权值 p2=p3;//替换p2,计算下一个三角形 } gx=gx/sumarea/3;//求的多边形重心 gy=gy/sumarea/3; printf("%.2lf %.2lf\n",gx,gy); } return 0; }
另外一种代码：
#include<iostream> #include<cmath> #include<cstdio> using namespace std; struct Point{ double x,y; }p[10005]; double Area(Point p1,Point p2,Point p3){//叉乘求三角形面积 return ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))/2.0; } int main() { int n,t; Point p0; p0.x=p0.y=0.0; scanf("%d",&t); while(t--){ scanf("%d",&n); double gx,gy,sumarea,area; gx=gy=sumarea=0; for(int i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y); for(int i=1;i<=n;i++){ area=Area(p0,p[i%n],p[i-1]);//与原点单个三角的面积 gx+=(p[i%n].x+p[i-1].x)*area;//重心乘以其权值(面积),由于每个都要除以3,所医院放在最后 gy+=(p[i%n].y+p[i-1].y)*area; sumarea+=area;//计算全部权值 } gx=gx/(sumarea*3);//求的多边形重心 gy=gy/(sumarea*3); printf("%.2lf %.2lf\n",gx,gy); } return 0; }
版权声明：本文博主原创文章，博客，未经同意不得转载。