多边形重心
例题：hdu 1115
给出一堆点，求多边形的重心。
我们可以把多边形划分为许多三角形。三角形的重心很简单：
x = ( x1 + x2 + x3 ) / 3 , y = ( y1 + y2 + y3 ) / 3
多边形的重心公式为：
借用大佬博客的图片：https://blog.csdn.net/u010499449/article/details/38168677
公式当中的行列式，其实就是三角形的面积，我们可以利用叉积来求。
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10;
int T,n;
double s,resx,resy;
struct node{double x,y;}t[N];
inline double corss(node a,node b,node c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
signed main(){
cin>>T;
while(T--){
scanf("%d",&n); resx=resy=s=0;
for(int i=1;i<=n;i++) scanf("%lf %lf",&t[i].x,&t[i].y);
for(int i=3;i<=n;i++){
double ts=corss(t[1],t[i-1],t[i])/2;
resx+=(t[1].x+t[i-1].x+t[i].x)*ts;
resy+=(t[1].y+t[i-1].y+t[i].y)*ts;
s+=ts;
}
printf("%.2lf %.2lf\n",resx/s/3,resy/s/3);
}
return 0;
}
查看11道真题和解析
投递三维家等公司10个岗位