地址:
解题思路:叉乘的运用
原理是在平面上取(0,0)来分割多边形为多个三角形,然后用叉乘来求三角形的面积(有向)再求和。这样的话可以把凸N多边形转化为N个三角形,然后求解N个三角形即可,输入顶点的顺序 无论是顺时针还是逆时针均可。
* 题目要求:计算多边形面积
* 方法:把n多边形分割成n-2个三角形,分别求和,然后相加
* 注意:分割的所有三角形有一个公共的顶点,这里选择0点位公共点
* 注:题中给出的点的顺序为逆时
* 叉乘的性质:设两向量P和Q
* 1.P ×Q > 0 则Q在P的逆时针方向
* 2.P ×Q < 0 则Q在P的顺时针方向
* 3.P ×Q = 0 则Q和P共线,方向可能相同也可能不相同
参考资料:
之所以不用海伦公式:有一个三角形,边长分别为a、b、c,三角形的面积S可由以下公式求得:S=√[p(p-a)(p-b)(p-c)] 而公式里的p为半周长: p=(a+b+c)/2
是由于1:计算量大。2:精度损失
1 #include2 #include 3 typedef struct point 4 { 5 int x,y; 6 }point; 7 point a[110];//n的范围限制 8 double area(point p,point q) 9 {10 return p.x*q.y-q.x*p.y;//叉乘计算面积的公式,简化的,是以(0,0)为起始点划分的11 }12 int main()13 {14 int i,n;15 double sum;16 while(~scanf("%d",&n)&&n)17 {18 for(i=0;i