首页 > 代码库 > [POJ 1385] Lifting the Stone （计算几何）
[POJ 1385] Lifting the Stone （计算几何）
题目链接：http://poj.org/problem?id=1385
题目大意：给你一个多边形的点，求重心。
首先，三角形的重心： ( (x1+x2+x3)/3 , (y1+y2+y3)/3 )
然后多边形的重心就是将多边形划分成很多个三角形，以三角形面积为权值，将每个三角形的重心加权平均。
注意：
pair<double,double>会MLE。。
fabs会损失精度？（这个我也不知道），因此在用向量叉积求三角形面积的时候最好是直接让面积求出来就是正的。。否则fabs就WA了。。。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 using namespace std; 6 typedef long long LL; 7 #define EPS 1e-8 8 #define X first 9 #define Y second10 11 typedef struct _POINT{ // 用pair<double,double>会MLE！！12 double first;13 double second;14 }POINT;15 16 typedef POINT VECTOR;17 double operator*(VECTOR x,VECTOR y){18 double res;19 res = x.X*y.Y-x.Y*y.X ;20 return res;21 }22 VECTOR operator-(POINT x,POINT y){23 VECTOR res;24 res.X = x.X - y.X ;25 res.Y = x.Y - y.Y ;26 return res;27 }28 29 const int MAX_N = 1000001;30 int T,N;31 POINT pt[MAX_N];32 33 POINT getCenter(POINT points[],int n){34 POINT res;35 double area,areamulx,areamuly;36 area = 0.0; areamulx = 0.0 ; areamuly = 0.0;37 for(int i=1;i<n-1;i++){38 VECTOR v1 = points[i]-points[0];39 VECTOR v2 = points[i+1]-points[i]; // 后面如果fabs会损失精度。。40 double tarea = v1 * v2 / 2.0;41 area += tarea;42 areamulx += (points[0].X+points[i].X+points[i+1].X)*tarea;43 areamuly += (points[0].Y+points[i].Y+points[i+1].Y)*tarea;44 }45 res.X = areamulx / (3.0*area);46 res.Y = areamuly / (3.0*area);47 return res;48 }49 50 int main(){51 scanf("%d",&T);52 while( T-- ){53 scanf("%d",&N);54 for(int i=0;i<N;i++){55 scanf("%lf%lf",&pt[i].X,&pt[i].Y);56 }57 POINT ans = getCenter(pt,N);58 printf("%.2lf %.2lf\n",ans.X+EPS,ans.Y+EPS);59 }60 return 0;61 }
[POJ 1385] Lifting the Stone （计算几何）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。