求任意多边形的重心
已知一多边形没有边相交，质量分布均匀。顺序给出多边形的顶点坐标，求其重心。
分析：
求多边形重心的题目大致有这么几种：
1，质量集中在顶点上。n个顶点坐标为(xi,yi)，质量为mi，则重心
X = ∑( xi×mi ) / ∑mi
Y = ∑( yi×mi ) / ∑mi
特殊地，若每个点的质量相同，则
X = ∑xi / n
Y = ∑yi / n
2，质量分布均匀。这个题就是这一类型，算法和上面的不同。
特殊地，质量均匀的三角形重心：
X = ( x0 + x1 + x2 ) / 3
Y = ( y0 + y1 + y2 ) / 3
3，质量分布不均匀。只能用积分来算，不会……
下面讨论这个题的解法：
以第一个顶点为基准，分别连接p[i]，p[i+1]，1<i<n。将多边形划分为若干个三角形。
若我们求出了每个三角形的重心和质量，可以构造一个新的多边形，顶点为所有三角形的重心，顶点质量为三角形的质量。这个新多边形的质量和重心与原多边形相同，即可使用第一种类型的公式计算出整个多边形的重心。
由于三角形的面积与质量成正比，所以我们这里用面积代替质量来计算。
现在有个问题就是，多边形有可能为凹多边形，三角形有可能在多边形之外。如何处理这种情况呢？
很简单，我们使用叉积来计算三角形面积，当三角形在多边形之外时，得到“负面积”就抵消掉了。
S =( x0*y1 + x1*y2 + x2*y0
- x1*y0 - x2*y1 - x0*y2 ) /2;
模版程序
# include<iostream>
# include<algorithm>
using namespace std;
const int maxNum = 1000000 +2;
struct point
{
double x, y;
};
struct point data[maxNum];
struct point bcenter(struct point pnt[], int n)【可以用来做模板】
{
point p, s;
double tp, area = 0, tpx = 0, tpy = 0;
p.x = pnt[0].x; p.y = pnt[0].y;
for (int i = 1; i <= n; ++i)
{
s.x = pnt[(i == n) ? 0 : i].x;
s.y = pnt[(i == n) ? 0 : i].y;
tp = (p.x * s.y - s.x * p.y);
area += tp / 2;
tpx += (p.x + s.x) * tp;
tpy += (p.y + s.y) * tp;
p.x = s.x;
p.y = s.y;
}
s.x = tpx / (6 * area);
s.y = tpy / (6 * area);
return s;
}
//OR:
This source is shared by zyd150
#include<stdio.h>
#include<math.h>
#define MAX 1000001
struct point
{
double x,y;
};
int n;
struct point p[MAX],v,ans;
void process(){
int i,j,k;
double s,ss=0;
ans.x=ans.y=0;
for(i=0;i<n;i++){
j=(i+1)%n;
v.x=(p[i].x+p[j].x)/3.0;
v.y=(p[i].y+p[j].y)/3.0;
s=(p[i].x*p[j].y-p[i].y*p[j].x)/2.0;
v.x*=s;v.y*=s;ss+=s;
ans.x+=v.x;ans.y+=v.y;
}
ans.x/=ss;ans.y/=ss;
if(fabs(ans.x)<0.000001) ans.x=0;
if(fabs(ans.y)<0.000001) ans.y=0;
printf("%.2lf %.2lf\n",ans.x,ans.y);
}
int main(){
int cas,i;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
process();
}
return 0;
}
#include<stdio.h>
#include<math.h>
#define MAX 1000001
struct point{
double x,y;
};
int n;
struct point p[MAX],v,ans;
void process(){
int i,j,k;
double s,ss=0;
ans.x=ans.y=0;
for(i=0;i<n;i++){
j=(i+1)%n;
v.x=(p[i].x+p[j].x)/3.0;
v.y=(p[i].y+p[j].y)/3.0;
s=(p[i].x*p[j].y-p[i].y*p[j].x)/2.0;
v.x*=s;v.y*=s;ss+=s;
ans.x+=v.x;ans.y+=v.y;
}
ans.x/=ss;ans.y/=ss;
if(fabs(ans.x)<0.000001) ans.x=0;
if(fabs(ans.y)<0.000001) ans.y=0;
printf("%.2lf %.2lf\n",ans.x,ans.y);
}
int main(){
int cas,i;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
process();
}
return 0;
}
int main()
{
int T,i,j,num;
struct point re;
scanf("%d",&T);
while(T--)
{
scanf("%d",&num);
for(i = 0; i < num ; i ++)
scanf("%lf %lf",&data[i].x,&data[i].y);
re = bcenter(data,num);
printf("%.2lf %.2lf\n",re.x,re.y);
}
return 0;
}