hdu 1115 Lifting the Stone 多边形的重心

发布时间:2014-10-22 14:21:28编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 1115 Lifting the Stone 多边形的重心",主要涉及到hdu 1115 Lifting the Stone 多边形的重心方面的内容,对于hdu 1115 Lifting the Stone 多边形的重心感兴趣的同学可以参考一下。

#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> using namespace std; const int maxn=1e6+10; struct node{ double x,y; }e[maxn]; double cross(double x1,double y1,double x2,double y2)//向量积 { return x1*y2-x2*y1; } int main() { int n,T; scanf("%d",&T); while(T--) { int i,j,k; scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf%lf",&e[i].x,&e[i].y);//逆时针输入 double sx=0,sy=0,area,sum=0; for(i=2;i<n;i++) { area=0.5*cross(e[i-1].x-e[0].x,e[i-1].y-e[0].y,e[i].x-e[0].x,e[i].y-e[0].y); sum+=area; sx+=area*(e[0].x+e[i-1].x+e[i].x)/3; sy+=area*(e[0].y+e[i-1].y+e[i].y)/3; } printf("%.2lf %.2lf\n",sx/sum,sy/sum); } return 0; } /* 向量积: a×b>0时,b在a的逆时针方向;a×b=0时,共线;a×b<0时,b在a的顺时针方向。 三角形重心:x=(x0+x1+x3)/3,y=(y0+y1+y2)/3; 已知一多边形没有边相交,质量分布均匀。顺序给出多边形的顶点坐标,求其重心。 将n+2多变形分成n个三角形,总面积为S,分重心为(xi,yi),分面积为si,则重心为X=(∑si*xi)/S,Y=(∑si*yi)/S; 凹多边形,如A(0,0),B(3,0),C(1,1),D(0,3),从(3,0)找三角形,可能不是再多边形内,如BCD。正好BC×BD<0,加上后可以消去BDA多加的部分。 所以这个公式也适合凹多边形。 */


上一篇:AndRoid五种存储方式
下一篇:搭建家用的OpenVPN服务器

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款