POJ 1474 Video Surveillance

POJ_1474

    对于半平面交的一些简明扼要的介绍可以参考这篇博客：javascript:void(0)。此外，这篇博客上介绍的还有我敲出的程序都只是比较好理解的O(n^2)的求半平面交的算法，对于O(nlogn)的算法可以参考朱泽园的论文。

    由于这个题目指明了多边形上的点是按顺时针序给出的，因而就不用再将每组数据都其统一成某个顺序了。

    POJ上这个题目INF不宜开太大，开太大比如0x3f3f3f3f会WA，但在ZOJ就没事，计算几何的精度问题太玄妙了，所以只好自己把握尺度啦。