前景提要： 继承上一张学习的凸包问题，下面我么来总结一下动态凸包的维护问题。
一些点已经构成了一个凸包之后，新加入||删除一些新的点的时候，会对原有的凸包产生一些影响，如果每次都重新把所有点都重新计算一遍凸包的话，那将非常耗费时间，以至于必定会WA，因此，我们就学习动态凸包的维护方法。
目录
前景提要：
观察总结凸包的维护
平衡树的维护
CF-70D-D. Professor's task（动态凸包板子）
洛谷-P2521-[HAOI2011]防线修建（离线查找+平衡树维护动态凸包）
观察总结凸包的维护 经过观察我们发现，每次新加入点的时候，只用对凸包的局部进行调整就行了，直接调整全部的凸包的话会花费很多不必要的时间和精力。因此有没有什么办法能够只调整凸包的部分呢？那就是找到需要调整的部分，然后以那个部分为中心开始调整，直到再次符合要求的时候即可。怎么才能快速找到要调整的部分呢？查找！平衡树！于是我们用平衡树来维护凸包，查找的时间就降低到了logn。！
首先得到一个最开始的凸包，我们用平衡树来维护这个凸包上的点，以极角序来作为第一关键字，长度作为第二关键字。来建立一颗平衡树。每次插入新点的时候，只用找到平衡树中距离这个新点最近的前面和后面的两个点，然后以这两个点为中心进行调整凸包。平衡树的查找时间复杂度为logn，这样只用进行局部调整就可以继续维持整个凸包的合理性了。
平衡树的维护 如何用平衡树来实现查找呢？如何建立平衡树呢？参考一下之前我的博客，伸展树维护平衡树：https://blog.csdn.net/qq_40482358/article/details/83305383
好了，现在我们已经回如何建立平衡树了。
但是平衡树的板子好长啊，光一个简单的板子就200多行了，就算格式紧凑一点也不好，自己写还容易出BUG。。不好不好。
当然我们可以不用自己写（那为什么放博客链接！！，当然是骗访问量啦！）
说笑说笑，其实学会平衡树之后对理解其他的数据结构也有很大的好处的，好处是巨大的。具体什么好处，太多了，就不多说了（有利于装逼）
C++《STL》内部的set集合就算是平衡树来维护的，因此我们可以借用一下set容器来实现我们的平衡树，而且平衡树的质量也有保证，不会出现一些奇奇怪怪的BUG...
至于如何用set维护我们的动态凸包，就是把点都加入set集合中，然后每次添加||删除的时候就是访问到set中距离新点最近的那几个点，（这几个点在凸包上），然后开始维护即可。
举个例子：如图所示，一开始存在一个凸包ABC（红色部分），然后新加入一个2号点，找到2号点附近的B和C点，然后删掉C点，加入2点；
再次新加一个1号点，找到A和2，发现无法删除，加入1号点即可。于是出现凸包AB21。
这里用两种方法进行排序，
1选择一个中心点，所有的点都在这个点的周围，以atan2的角度为第一关键字进行排序。但是因为涉及到了除法，因此会有精度损失，写一写水题还是可以的。
2.以凸包上的一个点为中间点进行极角排序，然后叉积进行第一关键字，这样就不会有精度损失。（但是我现在还不会QAQ）
直接上代码吧，首先是CF70D的一道板子题，大家也可以用来测试自己的板子：
CF-70D-D. Professor's task（动态凸包板子） 题目链接：http://codeforces.com/contest/70/problem/D
题目大意：给出n组情况，1添加一个点，2查看一个点是否在凸包内（包括边界）。对于每次查看，输出YES||NO。
思路：下面就是我的平衡树板子了。
ACCode：
#include
#include
#include
#include
#define ll long long
#define Pair pair
using namespace std;
const int INF32=0x3f3f3f3f;
const double EPS=1.0e-8;
const double PI=acos(-1.0);
struct Point{
double x,y;
Point(double _x=0,double _y=0){
x=_x;y=_y;
}
friend Point operator + (const Point &a,const Point &b){
return Point(a.x+b.x,a.y+b.y);
}
friend Point operator - (const Point &a,const Point &b){
return Point (a.x-b.x,a.y-b.y);
}
friend double operator ^ (const Point &a,const Point &b){
return a.x*b.y-a.y*b.x;
}
friend bool operator == (const Point &a,const Point &b){
return fabs(a.x-b.x) } }; struct V{ Point start,end; V(Point _start=Point(0,0),Point _end=Point(0,0)){ start=_start;end=_end; } }; Point Basic; set double Distance(Point a,Point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool operator < (Point a,Point b){ a=a-Basic;b=b-Basic; double Ang1=atan2(a.y,a.x),Ang2=atan2(b.y,b.x); double Len1=Distance(a,Point(0.0,0.0)),Len2=Distance(b,Point(0.0,0.0)); if(fabs(Ang1-Ang2) return Ang1 } set if(it==Set.begin()) it=Set.end(); return --it; } set ++it; return it==Set.end()?Set.begin():it; } int Query(Point p){ set if(it==Set.end()) it=Set.begin(); return ((p- *(Pre(it)))^(*(it)- *(Pre(it)))) } void Insert(Point p){ if(Query(p)) return ; Set.insert(p); set while(Set.size()>3&&((p- *(Nxt(it)))^(*(it)- *(Nxt(it)))) Set.erase(it);it=Nxt(Set.find(p)); }it=Pre(Set.find(p)); while(Set.size()>3&&((p- *(it))^(*(it)- *(Pre(it))))>-EPS){ Set.erase(it);it=Pre(Set.find(p)); } } int main(){ int q;scanf("%d",&q); Basic=Point(0,0); int oper;Point a,str[5]; for(int i=1;i<=3;++i){ scanf("%d%lf%lf",&oper,&str[i].x,&str[i].y); Basic=Basic+str[i];//Set.insert(str[i]); }Basic.x/=3.0;Basic.y/=3.0;q-=3; for(int i=1;i<=3;++i){ Set.insert(str[i]); } while(q--){ scanf("%d%lf%lf",&oper,&a.x,&a.y); if(oper==1){ Insert(a); } else{ if(Query(a)) printf("YES\n"); else printf("NO\n"); } } } 好了，动态凸包就到这里啦，什么？？删除怎么办？？不会啊，凉了，别写了，遇到了困难，就不做了，睡大觉！（雾雾雾 其实删除点的话，反过来看就是插入了，比如，还是上面的那张图： 我们一开始有1，2，A,B,C五个点构成了一个AB21凸包。第一次删掉点1，第二次删掉点2，最后剩一个ABC凸包。这反过来看。 最后有一个ABC凸包就是删掉点2的状态，加上点2就是删掉点1的状态，加上点1就是最初的状态，这样反过来求救可以转化成加点的问题了。 好了，赶紧做一道试试： 洛谷-P2521-[HAOI2011]防线修建（离线查找+平衡树维护动态凸包） 题目链接：https://www.luogu.org/problemnew/show/P2521 题目大意：中问题，就是我们上面说的那个情况。 思路：出题人真好啊，做出了一万个限制，限制了自己的数据范围，让我们感受到了来自大佬的关怀！赞美这个世界！ 没错！样例就是我们举了两个例子的那个图片！我就是懒！ 这里有和裸的维护动态凸包有所不同了，我们还要在维护凸包的周长，这个小问题：在ly大佬的***下，终于学会了如何维护周长了嘤嘤嘤... 当判断出来这个点在凸包外后，比如凸包ABC，新增点2，我们首先减去AC边，添上2C边，然后开始维护左边的部分。最后只剩下一部分A2边，再维护右半部分，删掉BC，加上2B，直到维护完成。 没错！又是这个图！我就增加了两条紫色线！（理直气壮！ 最后离线处理完反向输出就行了。 ACCode： // luogu-judger-enable-o2 //#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define Pair pair //#define max(a,b) (a)>(b)?(a):(b) //#define min(a,b) (a)<(b)?(a):(b) #define clean(a,b) memset(a,b,sizeof(a))// 水印 //std::ios::sync_with_stdio(false); // register const int MAXN=1e5+10; const int INF32=0x3f3f3f3f; const ll INF64=0x3f3f3f3f3f3f3f3f; const int MOD=1e9+7; const double EPS=1.0e-8; const double PI=acos(-1.0); struct Point { double x,y,vis,l; Point(double _x=0,double _y=0,double _vis=0,double _l=0) { x=_x;y=_y;vis=_vis;l=_l; } friend Point operator + (const Point &a,const Point &b) { return Point(a.x+b.x,a.y+b.y); } friend Point operator - (const Point &a,const Point &b) { return Point(a.x-b.x,a.y-b.y); } friend double operator ^ (Point a,Point b) { //向量叉乘 return a.x*b.y-a.y*b.x; } friend int operator == (const Point &a,const Point &b){ if(fabs(a.x-b.x) return 0; } }; struct V { Point start,end;double ang; V(Point _start=Point(0,0),Point _end=Point(0,0),double _ang=0.0) { start=_start;end=_end;ang=_ang; } friend V operator + (const V &a,const V &b) { return V(a.start+b.start,a.end+b.end); } friend V operator - (const V &a,const V &b) { return V(a.start-b.start,a.end-b.end); } }; Point Basic,Dots[MAXN]; set Pair Ask[MAXN]; int Vis[MAXN]; double ans[MAXN],ansl; double Distance(Point a,Point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool operator < (Point a,Point b){ a=a-Basic;b=b-Basic; double Ang1=atan2(a.y,a.x),Ang2=atan2(b.y,b.x); double Len1=Distance(a,Point(0,0)),Len2=Distance(b,Point(0,0)); if(fabs(Ang1-Ang2) return Ang1 } set if(it==Set.begin()) it=Set.end(); return --it; } set ++it; return it==Set.end()?Set.begin():it; } int Query(Point p){ set if(it==Set.end()) it=Set.begin(); return ((p- *(Pre(it)))^(*(it)-*(Pre(it)))) } void Insert(Point p){ if(Query(p)) return ; //不在凸包内部 Set.insert(p); ansl-=Distance(*(Nxt(Set.find(p))),*(Pre(Set.find(p)))); ansl+=Distance(*(Set.find(p)),*(Pre(Set.find(p)))); ansl+=Distance(*(Set.find(p)),*(Nxt(Set.find(p)))); set while(Set.size()>3&&((p- *(it))^(*(it)- *(Pre(it))))>-EPS){ ansl-=Distance(*(it),*(Nxt(it))); ansl-=Distance(*(it),*(Pre(it))); ansl+=Distance(*(Nxt(it)),*(Pre(it))); Set.erase(it);it=Pre(Set.find(p)); } it=Nxt(Set.find(p)); while(Set.size()>3&&((p- *(Nxt(it)))^(*(it)- *(Nxt(it)))) ansl-=Distance(*(it),*(Nxt(it))); ansl-=Distance(*(it),*(Pre(it))); ansl+=Distance(*(Nxt(it)),*(Pre(it))); Set.erase(it);it=Nxt(Set.find(p)); } // cout<<"erase last"< // for(it=Set.begin();it!=Set.end();++it){ // cout<<(*(it)).x<<" "<<(*(it)).y< // }cout<<"end Step"< } int main(){ double n,x,y;scanf("%lf%lf%lf",&n,&x,&y); Basic=Point(0,0);Basic=Basic+Point(n,0);Basic=Basic+Point(x,y); Basic.x/=3.0;Basic.y/=3.0;ansl=0; int m;scanf("%d",&m); for(int i=1;i<=m;++i){ scanf("%lf%lf",&Dots[i].x,&Dots[i].y); }int Q,oper,Index;scanf("%d",&Q); clean(Vis,0); for(int i=1;i<=Q;++i){ scanf("%d",&oper); if(oper==2){ Ask[i]=make_pair(2,0); } else{ scanf("%d",&Index); Ask[i]=make_pair(1,Index); Vis[Index]=1; } }Set.insert(Point(0,0));Set.insert(Point(n,0));Set.insert(Point(x,y)); ansl=Distance(Point(x,y),Point(0,0))+Distance(Point(x,y),Point(n,0)); for(int i=1;i<=m;++i){ if(Vis[i]==0){ Insert(Dots[i]); } }int k=0; for(int i=Q;i>=1;--i){ if(Ask[i].first==2){ ans[k++]=ansl; //printf("%lf\n",ans[k++]); } else{ Insert(Dots[Ask[i].second]); } } for(int i=k-1;i>=0;--i){ printf("%.2lf\n",ans[i]); } } /* 8 1 0 0 1 2 0 1 2 2 2 1 0 1 0 2 2 1 1 2 2 1 2 20 -1 */ 什么？？！！碰见强制在线的情况怎么办？？当然是发呆了，要不就是抱大腿，偷代码？？这辈子都不会偷代码的 最后也没见到完整的平衡树？？都说了太麻烦了！（其实是BUG没有调出来，还是太菜了啊）