异想天开

What's the true meaning of light, Could you tell me why

多边形重心问题

日期:2015-05-12 00:09:58
  
最后更新日期:2015-05-18 21:52:56
NYOJ
http://acm.nyist.net/JudgeOnline/problem.php?pid=3
描述
在某个多边形上,取n个点,这n个点顺序给出,按照给出顺序将相邻的点用直线连接, (第一个和最后一个连接),所有线段不和其他线段相交,但是可以重合,可得到一个多边形或一条线段或一个多边形和一个线段的连接后的图形;
如果是一条线段,我们定义面积为0,重心坐标为(0,0).现在求给出的点集组成的图形的面积和重心横纵坐标的和;
输入
第一行有一个整数0每组数据第一行有一个整数m<10000,表示有这个多边形有m个顶点;
输出
输出每个多边形的面积、重心横纵坐标的和,小数点后保留三位;
样例输入
3
3
0 1
0 2
0 3
3
1 1
0 0
0 1
4
1 1
0 0
0 0.5
0 1
样例输出
0.000 0.000
0.500 1.000
0.500 1.000
分析:
该题自己考虑时对凹多边形分类过于复杂,放弃了该想法。阅读:
http://blog.csdn.net/niushuai666/article/details/7454078
博文后,写了该解法。
需要了解的知识点。
多边形面积
多边形面积可以利用每条边与原点构成的三角形的面积之和,这些三角形有正有负。至于为什么可以这样,感觉就是“投影”的效果一样。这个三角形可以利用叉积来计算,对于点A(x1,y1),B(x2,y2),与原点的构成的三角形的面积:向量Ax向量B = x1*y2-x2*y1。
题外话:开始在考虑为什么可以这样,利用叉积满足交换律,平行的向量叉积为0向量。
多边形中心
多边形分隔为多个三角形后,重心为三角形的面积加权平均。可能有个疑问,某些面积为负数,是的,负数可以认为是在坐标轴上往相反的方向拉。
[code lang="cpp"]
#include<cstdio>
#include<cmath>
const int LEN=10001;
const double INF=0.001;
struct point{
double x;
double y;
};
struct point data[LEN]={{0.0,0.0}};

int sovle(){
int t;
double px,py,s;
scanf("%d",&t);
while (t--){
int n;
scanf("%d",&n);
s=0.0;
px=py=0.0;

scanf("%lf %lf",&data[0].x,&data[0].y);
for (int i=1; i<=n; ++i){
if (i<n){
scanf("%lf %lf",&data[i].x,&data[i].y);
}
double tmp=(data[i-1].x*data[i%n].y-data[i%n].x*data[i-1].y)/2;
s += tmp;
px += tmp*(data[i-1].x+data[i%n].x)/3;
py += tmp*(data[i-1].y+data[i%n].y)/3;
}

px = px/s;
py = py/s;
if ( fabs(s)<INF){
printf("0.000 0.000\n");
} else {
printf("%.3lf %.3lf\n",fabs(s),px+py);
}
}
return 0;
}

int main(){
sovle();
return 0;
}
[/code]