题目描述

近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务：

1. 给出你所有的A国城市坐标

2. A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了

3. A国上层询问对于剩下要保护的城市，修建防线的总经费最少是多少

你需要对每次询问作出回答。注意单位1长度的防线花费为1。

A国的地形是这样的，形如下图，x轴是一条河流，相当于一条天然防线，不需要你再修建

A国总是有两个城市在河边，一个点是(0,0)，一个点是(n,0)，其余所有点的横坐标均大于0小于n，纵坐标均大于0。A国有一个不在(0,0)和(n,0)的首都。(0,0),(n,0)和首都这三个城市是一定需要保护的。

说明

数据范围：

30%的数据m<=1000,q<=1000

100%的数据m<=100000,q<=200000,n>1

所有点的坐标范围均在10000以内, 数据保证没有重点

题解

要动态维护一个凸包。还要维护删除操作？

删除麻烦，可以离线，把删除变成插入操作。

一切就简单又自然了。

插入一个点t，就要找到凸包上的第一个大于等于横坐标x的点p，和第一个小于x的点q。即后继前驱。

题目很善良，河边点不会删除，所以一定在凸包上，不会有什么边界的锅。

如果在凸包里面那么就直接返回，怎么判断？

如果q和p的斜率在t和p的斜率，t和q的斜率大小之间的话，那么这个点一定不在凸包上。画图可以理解。

反之就一定在凸包上。

然后开始弹出点。不断向右比较斜率，再不断向左比较斜率。

最后把t加入凸包。

删除点的时候，实时更新防线的长度。

不要忘了最后把p、q之间的连边删除。

 

找前驱后继再删除，可以用splay实现。

但是没有必要，set完全可以支持。

代码：

#include
     
      using namespace std;const int N=100000+10;const double inf=19260817.0;int n,m;int cx,cy,far;double now;struct que{    int typ;    int id;    double ans;}q[2*N];struct po{    int x,y;    bool friend operator<(po a,po b){        return a.x
      
       s;set
       
        ::iterator it1,it2,it3;double dis(po a,po b){    return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));}double slo(po a,po b){
   //(x1,y1) -> (x2,y2)    if(a.x==b.x){        return a.y>b.y?-inf:inf;    }    return ((double)a.y-(double)b.y)/((double)a.x-(double)b.x);}void upda(po lp){    //lp.op();    //cout<<" size "<
        
         <
         
          =slo(lp,*it3)){        now-=dis(*it1,*it3);        s.erase(it1);        it1=it3;        it3--;    }    now+=dis(lp,*it1);    s.insert(lp);}int main(){    scanf("%d%d%d",&far,&cx,&cy);    scanf("%d",&n);int x,y;    for(int i=1;i<=n;i++){        scanf("%d%d",&x,&y);        a[i].x=x,a[i].y=y;    }    scanf("%d",&m);    for(int i=1;i<=m;i++){        scanf("%d",&q[i].typ);        if(q[i].typ==1) scanf("%d",&q[i].id),die[q[i].id]=1;    }    po st;st.x=0,st.y=0;s.insert(st);    po nd;nd.x=far,nd.y=0;s.insert(nd);    po ca;ca.x=cx,ca.y=cy;s.insert(ca);    now=dis(st,ca)+dis(ca,nd);    for(int i=1;i<=n;i++){        if(!die[i]){            upda(a[i]);        }    }    for(int i=m;i>=1;i--){        if(q[i].typ==2){            q[i].ans=now;        }        else{            upda(a[q[i].id]);        }    }    for(int i=1;i<=m;i++){        if(q[i].typ==2){            printf("%.2lf\n",q[i].ans);        }    }    return 0;}
         
        
       
      
     

总结：

现在我们有了一些斜率优化中，维护凸包的方法。

1.单调队列，适用于斜率有单调性，并且x要有单调性。才可以直接队头弹出，队尾插入。均摊O(1)

2.队列+二分。对于加入点的x有单调性，但是查询的斜率无单调性的时候，就要二分了。

二分到第一个斜率大于/小于查询斜率的点，作为决策点即可。除了队尾加入的时候，为了维护凸包所需，不会从队头弹出点。】

3.set（平衡树）维护。对于一般情况的凸包，可能加入的x在任何位置，查询什么凸包的周长，就必须用set了。

但是，对于斜率优化中，要查询一个第一个和后继/前驱比k大/小的点，因为set是按照x重载的运算符，不能直接lower_bound了。

所以，只能手写一棵splay，（就我所知）别无他法。

具体来说，一个splay树上的节点，按照x排序，而且必须还要记录和后继的斜率slope，和子树内所有后继斜率slope的最小值，便于直接二分。