题解 P1183 【多边形的面积】
这里提供一些思路
这道题是一道基础的计算几何。
很弱的一道题啊。
这道题最基础的方法是用剖分来做。剖分成若干个三角形。对每个三角形求面积。
求面积不要用海伦公式。原因是精度，貌似这道题不要求精度...那就无所谓了。
这种方法只适用于凸多边形
下面介绍一个能够求解任意多边形的方法，先做一下铺垫
用叉积求面积，对于两个向量a(x1,y1),b(x2,y2)
|ab|=x1y2-x2*y1
这求得的是两个向量围成的面积，一个平行四边形，所以要除以2
注意：这种方法求出来的是有方向的面积，就是有正负，注意注意
这种有正负经常是有用的
方法来了。还有证明。
计算方法：假设所有顶点为(x1,y1),(x2,y2)...(xn,yn)，把他们看做从原点指向这个点的向量，就是a1(x1,y1),a2(x2,y2)...an(xn,yn)，那么面积就是
|(a1a2+a2a3+...+a(n-1)an+ana1)/2|（最后的an*a1不要忘记，除以二不要忘记，绝对值不要忘记）
其实就是每一条线段对原点所围成的三角形的有向面积的和
但是....有可能乘法乘反，所以取一个绝对值保险
证明需要用到微元，就是微分
取一个小面积，并且把它看成一个点（够小么）
连接原点，这个点并延长，假设这个延长线（不包括原点到这个点）交多边形的边数为x
那么这个点就在，且只在这x条边的两个端点所求出的有向面积里面被包括
①如果这个点在多边形内，那么x一定为奇数（可证明）
（每个线段都是有方向的，从第i个点指向第i+1个点
那么就会有线段从射线左方向穿向右方向，又会有线段从射线左方向穿向右方向
第一种叫做左拐，第二种叫做右拐）
并且一定有关系：左拐数-右拐数=1（可证明）
对这个面积计算的时候会正着计算左拐数次，负着计算右拐数次
于是：正着计算次数-负着计算次数=1
又因为这个面积的大小恒定
所以这个面积计算了1次，正着
②如果这个点在多边形外，那么x一定为偶数（可证明）
类似的，左拐数-右拐数=0（可证明）
正着计算次数-负着计算次数=0
又因为这个面积的大小恒定
所以这个面积计算了0次，没有计数
综上，在多边形里面的面积计算一次，在多边形外面的面积计算0次，就正确计算出来了多边形的面积
算法其实只用保留现在处理的这条线段，所以可以把空间复杂度从O(n)降到O(1)