小结-计算几何
总结-计算几何
计算几何
做的题目很少, 而且模版也不熟. 所以还有这几天的时间, 把几个经典的算法弄熟弄懂, 模版能打出来就行了吧.
1. 凸包
2. 旋转卡壳
3. 半平面交
题目:
1. [codevs 1249] 多边形的面积 求多边形面积,
要理解叉积的意义.
2. [codevs 1298] 凸包周长 [codevs 3201] 奶牛代理商 XI 凸包周长
3. [codevs 1302] 小矮人(2002年CEOI中欧信息学奥赛) 旋转卡壳求对踵点
4. [codevs 3273] 两圆的交 这个题给我的启示就是见到计算几何的题目不一定非要套模版, 手推一下公式往往让问题变得很简单.
5. [CODEVS 3044] 矩形面积求并 离散化, 拆成不重叠的小矩形
6. [CODEVS 1244] 云中通信 奇葩的"译"字已经表明如果考到这种题目只能挂了. 思路了解一下吧
7. BZOJ-1007-水平可见直线-HN2008 有时斜截式比点+向量表示直线更直接方便.
8. BZOJ-1857-传送带-SCOI2010 三分法
9. BZOJ-2618-凸多边形-CQOI2006 半平面交的模版