Mato is No.1

原题地址

写了几天终于写出来了……（显然，我太弱了，请各位神犇不要鄙视）

在有加点的情况下，动态地维护凸包，有以下两种方法：
<1>维护上、下凸壳（本沙茶采用的方法）：
凸包可以拆成上、下凸壳，对它们分别维护。两个凸壳均按照下面定义的<关系（即先x增、再y增）排序，注意，两个凸壳的两端是相同的，均为整个凸包的最小点与最大点，除两端外，它们没有公共定点。
以上凸壳为例，设目前加进去的点是P，则有以下三种情况：
1)P小于上凸壳的最小点（这里，对于点"(x1, y1)<(x2, y2)"定义为：x1<x2或x1=x2且y1<y2），此时将P插入上凸壳，并从P开始从小到大遍历新的上凸壳，将那些旋转方向不对的点删掉；
2)P大于上凸壳的最大点（这里，对于点"(x1, y1)>(x2, y2)"定义为：x1>x2或x1=x2且y1>y2），此时将P插入上凸壳，并从P开始从大到小遍历新的上凸壳，将那些旋转方向不对的点删掉；
3)P位于上凸壳的最小点与最大点之间：此时找到上凸壳中，小于等于P的最大点L和大于P的最小点R，判断PL转向PR是否为逆时针，若为逆时针，则P在上凸壳外，插入上凸壳，并分别向左右两个方向遍历，将旋转方向不对的点删掉；
对于下凸壳，1)和2)一样，3)反过来搞即可。注意在找前趋L和后继R的时候，可以顺便判断出来P是否在上、下凸壳上，若在凸壳上则不插入。
显然，这当中有插入、删除、找值的前趋和后继等操作，因此需要用平衡树。由于每个点最多只会被插入一次、删除一次，且遍历就意味着删除，因此总时间复杂度为O(NlogN)。为了加快速度，可以在平衡树（Splay Tree）中维护子树的最小、最大结点。
问题是，这种方法写起来是很复杂的，因为要维护两棵平衡树。

<2>极角法（Orz！！）：
如果凸包面积大于0，可以在其内部选一个点作为定点，然后将凸包上所有点按照到这个定点的极角递增排序，用一棵平衡树维护。
加入新点P时，首先得出P到定点的极角，在平衡树中找到其前趋和后继，然后作叉积判断P是否在外部，若不在外部则不插入，否则插入，并且从这个前趋与这个后继开始，分别向两端删掉旋转方向不对的多余点。注意，虽然凸包是一个环，但由于按照极角排序了，在平衡树中仍只能作为链来维护，这样就会出现，在找前趋和后继的时候，如果在两端找不到，需要循环，到另一端去找，而且在遍历的时候，到头了也要回到另一端。
这种方法的时间复杂度也是O(NlogN)，且由于只要维护一棵平衡树，代码量减小了很多（木有必要像下面的烂代码一样每个操作都加上bool _和N多的[_]了，虽然多了点循环的特判）。

当然，本题是可以不用平衡树的，而用线段树——因为可以离线。
还有一个问题就是本题的维护面积问题。面积的2倍可以用各边两端点关于任意定点的叉积之和得出，前提是端点按照逆时针排列（最后结果的正负只与端点排列顺序有关，与这个定点在哪无关），因此，对于有边加入或删除的时候，就可以顺便维护出来，当然在有三角形变化的时候可以直接维护三角形。

动态凸包的最主要应用就是那些用凸壳或曲线凸壳优化的DP，虽然这种DP大多数时候只需要维护上或下凸壳就行了囧……比较典型的应用有：
NOI2007 cash（动态维护凸壳，但本题可以用分治转成离线，从而直接Graham构造解决）
NOI2009 poet（维护曲线凸壳，容易证明这种绝对值P次函数的曲线符合交点只有一个的性质，且对称轴是越来越右，所以可以直接用队列维护……MS它是一种有用模型的代表）
BZOJ2149 拆迁队（由于合法决策要满足三个条件：决策阶段较小、A值较小、F值严格比目前阶段F值小1，因此需要变序，按照A的递增序插入决策射线，维护可以离散化后用线段树，也可以根据A值即为斜率且递增，直接用栈维护凸壳。当然，本题也需要分治转成离线）
CEOI2011 ballons（本题的效果值曲线为顶点在X轴上的开口向上的抛物线，由于对称轴x是递增的，所以可以只维护右半部分，一个决策插入后影响的是一个区间，可以离散化后用线段树解决。当然，本题如果对称轴x不递增才好玩呢囧……）

代码：