Mato is No.1

原題地址

寫了幾天終于寫出來了……（顯然，我太弱了，請各位神犇不要鄙視）

在有加點的情況下，動態(tài)地維護凸包，有以下兩種方法：
<1>維護上、下凸殼（本沙茶采用的方法）：
凸包可以拆成上、下凸殼，對它們分別維護。兩個凸殼均按照下面定義的<關(guān)系（即先x增、再y增）排序，注意，兩個凸殼的兩端是相同的，均為整個凸包的最小點與最大點，除兩端外，它們沒有公共定點。
以上凸殼為例，設(shè)目前加進去的點是P，則有以下三種情況：
1)P小于上凸殼的最小點（這里，對于點"(x1, y1)<(x2, y2)"定義為：x1<x2或x1=x2且y1<y2），此時將P插入上凸殼，并從P開始從小到大遍歷新的上凸殼，將那些旋轉(zhuǎn)方向不對的點刪掉；
2)P大于上凸殼的最大點（這里，對于點"(x1, y1)>(x2, y2)"定義為：x1>x2或x1=x2且y1>y2），此時將P插入上凸殼，并從P開始從大到小遍歷新的上凸殼，將那些旋轉(zhuǎn)方向不對的點刪掉；
3)P位于上凸殼的最小點與最大點之間：此時找到上凸殼中，小于等于P的最大點L和大于P的最小點R，判斷PL轉(zhuǎn)向PR是否為逆時針，若為逆時針，則P在上凸殼外，插入上凸殼，并分別向左右兩個方向遍歷，將旋轉(zhuǎn)方向不對的點刪掉；
對于下凸殼，1)和2)一樣，3)反過來搞即可。注意在找前趨L和后繼R的時候，可以順便判斷出來P是否在上、下凸殼上，若在凸殼上則不插入。
顯然，這當(dāng)中有插入、刪除、找值的前趨和后繼等操作，因此需要用平衡樹。由于每個點最多只會被插入一次、刪除一次，且遍歷就意味著刪除，因此總時間復(fù)雜度為O(NlogN)。為了加快速度，可以在平衡樹（Splay Tree）中維護子樹的最小、最大結(jié)點。
問題是，這種方法寫起來是很復(fù)雜的，因為要維護兩棵平衡樹。

<2>極角法（Orz！！）：
如果凸包面積大于0，可以在其內(nèi)部選一個點作為定點，然后將凸包上所有點按照到這個定點的極角遞增排序，用一棵平衡樹維護。
加入新點P時，首先得出P到定點的極角，在平衡樹中找到其前趨和后繼，然后作叉積判斷P是否在外部，若不在外部則不插入，否則插入，并且從這個前趨與這個后繼開始，分別向兩端刪掉旋轉(zhuǎn)方向不對的多余點。注意，雖然凸包是一個環(huán)，但由于按照極角排序了，在平衡樹中仍只能作為鏈來維護，這樣就會出現(xiàn)，在找前趨和后繼的時候，如果在兩端找不到，需要循環(huán)，到另一端去找，而且在遍歷的時候，到頭了也要回到另一端。
這種方法的時間復(fù)雜度也是O(NlogN)，且由于只要維護一棵平衡樹，代碼量減小了很多（木有必要像下面的爛代碼一樣每個操作都加上bool _和N多的[_]了，雖然多了點循環(huán)的特判）。

當(dāng)然，本題是可以不用平衡樹的，而用線段樹——因為可以離線。
還有一個問題就是本題的維護面積問題。面積的2倍可以用各邊兩端點關(guān)于任意定點的叉積之和得出，前提是端點按照逆時針排列（最后結(jié)果的正負只與端點排列順序有關(guān)，與這個定點在哪無關(guān)），因此，對于有邊加入或刪除的時候，就可以順便維護出來，當(dāng)然在有三角形變化的時候可以直接維護三角形。

動態(tài)凸包的最主要應(yīng)用就是那些用凸殼或曲線凸殼優(yōu)化的DP，雖然這種DP大多數(shù)時候只需要維護上或下凸殼就行了囧……比較典型的應(yīng)用有：
NOI2007 cash（動態(tài)維護凸殼，但本題可以用分治轉(zhuǎn)成離線，從而直接Graham構(gòu)造解決）
NOI2009 poet（維護曲線凸殼，容易證明這種絕對值P次函數(shù)的曲線符合交點只有一個的性質(zhì)，且對稱軸是越來越右，所以可以直接用隊列維護……MS它是一種有用模型的代表）
BZOJ2149 拆遷隊（由于合法決策要滿足三個條件：決策階段較小、A值較小、F值嚴格比目前階段F值小1，因此需要變序，按照A的遞增序插入決策射線，維護可以離散化后用線段樹，也可以根據(jù)A值即為斜率且遞增，直接用棧維護凸殼。當(dāng)然，本題也需要分治轉(zhuǎn)成離線）
CEOI2011 ballons（本題的效果值曲線為頂點在X軸上的開口向上的拋物線，由于對稱軸x是遞增的，所以可以只維護右半部分，一個決策插入后影響的是一個區(qū)間，可以離散化后用線段樹解決。當(dāng)然，本題如果對稱軸x不遞增才好玩呢囧……）

代碼：