POJ2451【基础】
题目大意:
给出一个二维平面上的有向直线<s,e>,表示从直线上的 s 点指向 e 点。这样的
直线规定了一个半平面,即其左侧(<s,e>的逆时针方向)。现在给出 n
(1<=n<=20000)个半平面,求它们在原点到(10000,10000)这一块正方形内的
交的面积。
输入:
有若干组测试数据。每一组测试数据第一行有一个整数 n,接下来有 n 行,每
一行有四个空格分隔的小数 x1 y1 x2 y2,表示一条直线 s 点和 e 点的 x y 坐
标。
输出:
每一组测试数据输出一行,包含一个一位小数,即半平面的交的面积。
题解:
这是一题半平面交的裸模板题,据网上的说法是 ZZY 大神给他的 O(nlogn)的新
排序增量算法专门出的题,后来数据被改弱了,O(n^2)也可以过。这里我用的
是 ZZY 的排序增量算法写了一个半平面交的模板。由于算法有点复杂,
这里讲不清楚,给出两个我参考的网址:
http://blog.csdn.net/accry/article/details/6070621
http://blog.csdn.net/non_cease/article/details/7798011 (我的模板主
要从这里改过来的)
POJ3335【基础】
题目大意:
给一个有 n 个点(1<=n<=100)多边形,求这个多边形的核是否存在。所谓多边形
核,指的是多边形内的一个点集(一片区域),这些点集中的任意一点与多边
形边上任意一点的连线都不会与多边形的边相交。
输入:
第一行有一个整数 t,表示有 t 组测试数据。每一组测试数据一行,第一个整
数 n,接下来有 n 对空格分隔的整数,表示一个点的 x y 坐标,点按顺时针顺
序给出。
评论0