题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=3
题目分析:好吧,这个题目基本上话了我一个小时去回顾以前学过的几何知识。下面我们来一点一点的分析。
1)重心就是重量的中心。其定义就是对整个图形分别从x方向和y方向进行密度积分,然后除以总面积,就得到了重心的x坐标和y坐标。这里由于图形每一点都是一样的,也就说说密度平均。好吧,说到积分,很多人就头疼了,好吧,我也烦这个。OK,换一个说法。多边形一定可以分成若干个不相交的三角形吧。其实通过重心和多边形的每一个点相连,就得到了我们要的三角形了。
2)把每一个三角形看成一个质心,那么我们刚刚所说的对密度进行积分其实分两个,x方向和y方向。那么x方向的积分就变成了对所有的三角形把 三角形的面积*该三角形重心的x坐标 的积加起来,同理y方向的积分就变成了对所有三角形把 三角形的面积*该三角形重心的y坐标 的积加起来。
3)每个三角形的面积怎么求?
其实在高中的时候我们就知道,已知三角形的两个边a,b。s=a*b*sin(ab所夹的角)。当然大学肯定学过叉乘。a×b=|a|*|b|*sin(ab所夹的角)。这里需要注意叉乘是有方向的,所以这个角必须是从a到b并且符合右手定律的那个角。
4)三角形的重心怎么求?
这个很简单啦!三个点的坐标的平均就可以了。公式不用我说了吧。
5)关键地方来了~
我开始说的把多边形分成若干个三角形的方法是让重心与每个点相连,但是这里重心是我们要求的东西,所以这样肯定不行。不过聪明的你肯定想到了以多边形的第一个点为准,然后分别与其它各点相连,然后形成的向量就是(point[0].x-point[i].x,point[0].y-point[i].y)和(point[0].x-point[i+1].x,point[0].y-point[i+1].y)。。或者说相邻的三个点就可以组成一个三角形则形成的向量就是(point[i].x-point[i-1].x, point[i].y-point[i-1].y)和(point[i].x-point[i+1].x,
point[i].y-point[i+1].y)。OK,现在我告诉你,这两个方法都弱爆了。由于叉乘的特殊性质,前面我说的,它是有方向的,所以我们可以把这个相对的点移到任何一个角落。那么这个点既然是任意的,为什么不放在原点呢?你会奇怪为什么会这样。因为a×b=-b×a。so,你画画图试试~~~
OK~说了那么多累死我了,要还是不懂,对照着代码看吧~~
#include<stdio.h> #include<math.h> const int N = 10005; typedef struct { double x; double y; }POINT; POINT point[N]; inline double CrossProduct(int i) { return point[i].x * point[i + 1].y - point[i + 1].x * point[i].y; } int main() { int n,t; int i; double temp; double area,x,y; scanf("%d", &t); while(t--) { scanf("%d",&n); for(i = 0; i < n; ++i) scanf("%lf %lf",&point[i].x, &point[i].y); point[n].x = point[0].x;//记下第一个点,形成循环 point[n].y = point[0].y; area = 0.0; x = 0.0; y = 0.0; for(i = 0; i < n; ++i) { temp = CrossProduct(i) / 2.0; area += temp; x += temp * (point[i].x + point[i + 1].x) / 3.0; y += temp * (point[i].y + point[i + 1].y) / 3.0; } area = fabs(area);//我说了,叉乘有方向,最后记得取绝对值 if(area < 0.0000001) printf("0.000 0.000\n"); else printf("%.3lf %.3lf\n", area, fabs(x + y) / area); } }