题目大意是给出一个n个点坐标，问能否组成一个封闭的多边形，如果能求出该多边形的面积。
计算多边形的面积可以根据三角剖分来利用向量的叉积运算来计算（郁闷，市选时不会这个丢了35分……）。而判断能否构成多边形实际上只需要判断点数是否少于3，如果是则判不能；以及判断任意两条非相邻线段是否会相交即可。不需要判断多边形端点重复和端点在线段上的情况，只需要将判断线段相交那部分修改一下（将两线段有一交点也视为线段相交）即可达到相同的效果。
2999114 2008-07-23 15:38:32 Accepted 1010 FPC 00:00.14 432K IwfWcf@LZOI
题目大意是给出一个n边形各个点的坐标，接下来有m个询问，回答每个询问中的点是否在n边形内。
这是最基本的计算几何题了，一般有两种方法：射线法和环顾法（又称转角法）。虽然两者的时间复杂度都是线性的，但环顾法要慢很多。而射线法实现时并不需要真的设一个极远的端点来利用判断线段相交的方法判断是否有交点，只需利用快速排斥实验的原理以及叉积的特性即可，规定只有在某一边的计算穿点数。在这一题中我对于穿越端点的处理方法是不对其进行计数处理，但实际上可以构造出数据使我的程序出错，更为严谨的方法应该是特判或者用平移法将其平移一段很小的距离（参见黑书上的具体说明）。另外如果点在n边形的端点或边上可直接判定在形内。
2998704 2008-07-23 13:42:44 Accepted 1081 FPC 00:00.00 408K IwfWcf
博文
所有评论
