[笔记] 树链剖分
后缀数据结构 练习记

凸包凸壳相关 (Updating)

RXDoi posted @ 2015年4月19日 21:22 in 笔记 , 174 阅读

    最近在学凸包凸壳相关,开篇博文。

求凸包:

Graham Scan,按水平序排序,栈维护上下凸壳后拼起来。可以很好地处理特殊情况(三点共线之类)。

平衡树维护动态凸包:

把上面的过程用平衡树维护,插入一个点时找它前驱后继,往左右不停删掉不合法的。

听起来很简单,实现起来奇萎无比……我和这东西搏斗了一天……唉代码能力弱真是太伤了……不过重写了2、3遍,好歹研究出了一种比较优秀的写法。

BZOJ 1249:[SGU2777 HERO 动态凸包]:模版题,插入一个点的时候维护上下凸壳,要分类讨论:插在最前面/中间/最后面。先在左右删掉不合法的点,然后:插在前后的话这个点一定在新的凸壳上,否则判下它在当前凸壳的左右决定是否插进去。上下凸壳的部分差不多但是大于小于号不一样,于是我用两个Set,S[f=0..1]来维护,一开始想的是中间所有判断语句都把表达式的值^f。但是等于0,即三点共线的情况不能简单忽略过去,然后我又写了个cmp返回1,0,-1表示与0的大小关系,乱搞搞了搞终于搞好了……代码没到2k,BZOJ上跑了暂时#1。这是我第一道严格BZOJ #1。有点开心。

BZOJ 2300:[HAOI2011 防线修建]:比前一题还要简单,只要维护上凸壳,一定插入在中间。离线就行了。 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter