1.動态凸包是一類經典的題目，題目的大概意思就是：在添加和删除平面上的一些點，然後詢問這些點構成的凸包的資訊。典型題目：HAOI 2011 建構。有多種寫法，可以用Splay維護，也可以用set維護。我們來讨論一下如何使用set維護動态凸包，但是有一個缺陷，就是隻支援添加點，删除點的是不行的，但是我們可以把操作離線下來，倒着掃，删點就成了加點。
(1)首先我們把所有的點按照x排序，x相同的按照y排序。假設我們已經得到了某個凸包：
現在加入x點，
顯然，x點是要凸包上的一個點，我們首先在set内lowerbound一個點，r，然後r像後邊退一個得到l。因為我們是看出來這個點的确實需要被加入凸包集合内，但是如何判斷呢？
做rx向量，lx向量，我們可以看出來，lx*rx(叉乘）是一個正的數字，直白點就是說rx轉向rx的角度是一個小于180的角，那麼這個點就要被加入凸包内，否則不加入。加入以後，我們如何建構新的凸包呢？方法類似，因為我們已經得到了l,r.以l為例：
将l向左推移，得到l1,發現l1x轉向lx的夾角的sin值也是一個正值，是以l1繼續留在凸包内部，否則從集合删除這個點。這樣把l一直左推到起點就完成了左半部分凸包的更新，右半部分類似。這樣每次更新的複雜度是O(size(set))的。是以這種方法雖然比Splay好實作，但是極限資料時可能會不是很好。
/*
凸包被存在st中，st是一個set。point結構體重載了*，重載為叉積。it為宏定義，為set的疊代器
ans：凸包的周長，calc()為計算兩點間距離的函數。動态維護凸包的周長
*/
inline void insert(point x)
{
it r = st.lower_bound(x), l = r, t;
l--;
if ((*r - *l) * (x - *l) < 0)return;
ans -= (*r - *l).calc();
while (1)
{
t = r, r++;
if (r == st.end())break;
if ((*r - x) * (*t - x) > 0)break;
ans -= (*r - *t).calc();
st.erase(t);
}
while (l != st.begin())
{
t = l, l--;
if ((*l - x) * (*t - x) < 0)break;
ans -= (*l - *t).calc();
st.erase(t);
}
st.insert(x);
l = r = st.find(x);
l--, r++;
ans += (*r - x).calc(), ans += (*l - x).calc();
}