任意多边形的面积

*这是第一篇关于ACM-ICPC的练习笔记。包括本篇在内的未来的所有笔记,主要内容都将为我自己练习的时候所遇到的新知识、技巧等。 给定多边形的顶点坐标(有序),让你来求这个多边形的面积,你会怎么做? 我们知道,任意多边形都可以分割为N个三角形,所以,如果以这为突破点,那么我们第一步就是把给定的多边形,分割为数个三角形,分别求面积,最后累加就可以了,把多边形分割为三角形的方式多种多样,在这里,我们按照如下图的方法分割: S点作为起始点(点1),a->e依次作为点2,3……。 一个三角形的面积是怎样的呢? 根据线性代数的知识,我们有如下的三角形面积公式,称之为有向面积(signed area): 将这个行列式以第三列展开可以得到: 这就是以点1、2、3构成的三角形的有向面积(点如果是顺时针给出,有向面积为负,逆时针给出,有向面积为正),那么继续我们的工作,通过三角形的面积公式,来得到多边形的面积公式: 对于图1而言,多边形的面积就是: S(1-&g...