频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu1115(多边形重心算法)
2014-11-05 11:02:00           
收藏   我要投稿

题目意思:

给出一个n边形的n个顶点,求出这个n边形的重心坐标。

 

 

题目分析:

/**

 

*①质量集中在顶点上
* 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
#include
#include
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 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 ,gx,gy);
}
return 0;
}

第二种代码:

#include
#include
#include
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 ,gx,gy);
}
return 0;
}


 

点击复制链接 与好友分享!回本站首页
相关TAG标签 多边形 重心 算法
上一篇:NYOJ 49 开心的小明(经典01背包水题)
下一篇:BZOJ 1458 士兵占领 Dinic最大流
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站