USACO 5.1.1Fencing the Cows
凸包模板题,直接用melkman算法就OK了,melkman比其他的两种要好写[至少我这么认为],而且复杂度低.对于melkman算法就是用一个双端队列一直维护,使得在这个双端队列里面的一直是一个凸包[如果是乱序的就必须先排好序,可以就按y坐标排序如果需要再按x坐标排序,下面会有为什么要排序的一个例子].首先我们选三个点[这三个点不共线],入队列,保证队头一段时左转,队尾一端是右转.然后就把整个平面分成了下面的这样一个区域了,
首先选前三个不共线的点入队,对头保证左转弯,队尾满足右转弯,然后队的两端是同一个点,也就是加入的最后一个点.之后就把整个平面分成了如上几个区域,I,II,III,IV,V.但是排好序之后V是不可能出现的[那里为什么要排序,也是为了防止出现V这种情况],也就是说现在只可能出现其他的四个区域了,但是区域I是不行的,因为进入了凸包的内部,如果在II区域的话,那么队顶退出直至满足凸包性质为止[左转弯],III区域的话就是操作队尾,然后IV区域的话就要同时操作队顶和队尾了.这样就OK了.然后这题就是要输出凸包的周长,有了凸包,周长神马的都是浮云了~~~
