Codeforces 70D 动态凸包 (极角排序 or 水平序)
题目链接：http://codeforces.com/problemset/problem/70/D
本题关键：在log(n)的复杂度内判断点在凸包 或 把点插入凸包
判断：平衡树log(n)内选出点所属于的区域
插入：平衡树log(n)内选出点所属于的区域， 与做一般凸包的时候类似，分别以该点向左右两边进行维护，
一直删除不满足凸包的点，直到所有点满足凸包为止。
水平序：
可以用2个平衡树分别维护上下2个半凸包，具体实现时可以把其中一个半凸包按y轴对称以后，那么2个半凸包的维护就是同一种方法，写2个函数就ok了。
具体平衡树可以用set或map，用STL以后边界处理有点烦，需要注意。
水平序的凸包有一个特点（如按x排序）：对于上下凸包(分开来看)，x相同的点只有一个。所以用set维护比较麻烦，用map维护相对容易一点。
极角序：
之前给你的3个点一定是插入的，可以选它们的中心点o作为之后的凸包中心，按o进行极角排序。
之后的做法就跟 “本题关键” 的做法一致。
以下给出3份不同的代码：
set代码：
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <set>using namespace std;typedef long long ll;struct point {int x, y;ll d;double z;}o, a[5], p;typedef set <point>:: iterator iter;bool operator <(const point &a, const point &b) {return a.z < b.z || (a.z == b.z && a.d < b.d);}ll cross(point o, point a, point b) {return (ll)(a.x-o.x)*(b.y-o.y)-(ll)(a.y-o.y)*(b.x-o.x);}set <point> st;iter L(iter x) {if(x == st.begin()) x = st.end();x--;return x;}iter R(iter x) {x++;if(x == st.end()) x = st.begin();return x;}int q, op;int main() {scanf("%d", &q);for(int i = 0; i < 3; i++) { scanf("%d%d%d", &op, &a[i].x, &a[i].y); o.x += a[i].x; o.y += a[i].y; a[i].x *= 3; a[i].y *= 3;}for(int i = 0; i < 3; i++) { a[i].d = (ll)(a[i].x-o.x)*(a[i].x-o.x)+(ll)(a[i].y-o.y)*(a[i].y-o.y); a[i].z = atan2(a[i].y-o.y, a[i].x-o.x); st.insert(a[i]);}q -= 3;while(q--) {scanf("%d%d%d", &op, &p.x, &p.y);p.x *= 3; p.y *= 3;p.z = atan2(p.y-o.y, p.x-o.x);p.d = (ll)(p.x-o.x)*(p.x-o.x)+(ll)(p.y-o.y)*(p.y-o.y);iter i = st.lower_bound(p), j;if(i == st.end()) i = st.begin();j = L(i);if(op == 2) {if(cross(*j,p,*i)<=0) puts("YES");else puts("NO");continue;}if(cross(*j,p,*i)<=0) continue;st.insert(p);iter cur = st.find(p); i = L(cur); j = L(i);while(cross(*j, *i, *cur) <= 0) {st.erase(i);i = j; j = L(j);}i = R(cur); j = R(i);while(cross(*j, *i, *cur) >= 0) {st.erase(i);i = j; j = R(j);}}return 0;}