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不遞增才好玩呢囧……）

代碼：