http://www.lydsy.com/JudgeOnline/problem.php?id=2300

题意：给点，有以下操作:删去一个点，询问这些点构成凸包的周长。

思路:用splay维护上凸壳，splay排序的关键字是X，同时还要记录每个点与左右点的斜率，当加入一个点时，我们找到它应该在的X的位置，一个个减掉左边，一个个减掉右边，符合条件就是当左边的斜率大于右边的斜率，就表明它在凸包上。

PS:如果当前加入点的左边斜率小于右边斜率，说明它在凸包内，可以直接删掉这个点。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          struct node{     int id,val,opt;}q[200005];struct point{    double x,y;}p[200005];const double eps=1e-9;int tmp,root;double c[200005],xx[200005],yy[200005],ans,rk[200005],lk[200005];int n,ch[200005][2],fa[200005],vis[200005];int read(){    int t=0,f=1;char ch=getchar();    while (ch<'0'||ch>'9'){
   if (ch=='-') f=-1;ch=getchar();}    while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}    return t*f;}void rotate(int x,int &rt){     int y=fa[x],z=fa[y],l,r;     if (ch[y][0]==x) l=0;else l=1;r=l^1;     if (y!=rt){        if (ch[z][0]==y) ch[z][0]=x;else ch[z][1]=x;     }else rt=x;     fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;     ch[y][l]=ch[x][r];ch[x][r]=y;}void splay(int x,int &rt){     while (x!=rt){        int y=fa[x],z=fa[y];        if (y!=rt){           if (ch[z][0]==y^ch[y][0]==x) rotate(x,rt);           else rotate(y,rt);        }        rotate(x,rt);     }}void find(int k,double X){    if (!k) return;    if (xx[k]
          
           =lk[id]){getslope(x,y);fa[id]=0;ch[y][0]=0;ans+=dis(x,y);return;} splay(id,root); root=id; x=pre(id); ans+=dis(x,id); while (lk[x]<=rk[x]&&x){ y=pre(x); splay(y,ch[x][0]); ans-=dis(x,id); ans-=dis(x,y); ans+=dis(y,id); fa[x]=ch[x][0]=ch[x][1]=0; ch[id][0]=y;fa[y]=id; getslope(y,id); x=y; } x=suc(id); ans+=dis(x,id); while (lk[x]<=rk[x]&&x){ y=suc(x); splay(y,ch[x][1]); ans-=dis(x,id); ans-=dis(x,y); ans+=dis(y,id); fa[x]=ch[x][1]=ch[x][0]=0; ch[id][1]=y;fa[y]=id; getslope(id,y); x=y; }}int main(){ int m=read(),x=read(),y=read(); n=read(); for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); int T=read(); for (int i=1;i<=T;i++){ q[i].opt=read(); if (q[i].opt==2) continue; q[i].id=i;q[i].val=read();vis[q[i].val]=1; } insert(0,0,1); insert(m,0,2); insert(x,y,3); for (int i=1;i<=n;i++) if (!vis[i]){ insert(p[i].x,p[i].y,i+3); } int top=0; for (int i=T;i>=1;i--){ if (q[i].opt==2){ c[++top]=ans; }else{ insert(p[q[i].val].x,p[q[i].val].y,q[i].val+3); } } for (int i=top;i>=1;i--) printf("%.2f\n",c[i]);}