【BZOJ2300】【HAOI2011】防线修建

题目大意：给你m+3个点，有q个操作，每次要么询问当前点集构所构成的上凸壳总长度，要么在当前点集中删除一个点。

这题是吼题啊！！！

刚开始想着如何正常地做，考虑过用线段树维护一个区间内的凸包，发现并不行，要另请高明。

后来发现，这题并没有强制在线要求，我们不妨将所有的询问反过来处理。首先将从头到尾都没有被删除的点加入该凸包，然后将询问倒序处理，将原先的删点操作改为加点操作，随后动态维护该凸包并维护上凸壳总长度，需输出的答案压入一个栈中，最后逐个弹出输出即可。

至于如何动态维护凸包。本题有一个很特殊的条件：所有点坐标的x,y值均大于0，且必有一个点坐标为（0,0）。故我们可以用一个set维护当前在凸包上的点，当需要加入一个点k时，借助lower_bound找到与该点相邻夹角的两个点，直接进行维护即可。实现细节较为复杂，强烈建议先工整地将维护方法写在草稿纸上！！

PS：这次发现set容器的iterator有一些神奇的性质，假定有一个迭代器指针it，其后继为it1，在it未更新时，若有一个元素插入在it和it1之间，那么it1仍将认为其后继为it1而非新插入的元素，需要用某些方法更新下it(没有1a的元凶)

 #include<bits/stdc++.h>

 #define M 210000

 using namespace std;

 struct node{

     int x,y; node(){x=y=;}

     node(int xx,int yy){x=xx; y=yy;}

     friend node operator -(node a,node b){return node(a.x-b.x,a.y-b.y);}

     friend int operator *(node a,node b){

         return a.y*b.x-a.x*b.y;

     }

     friend bool operator <(node a,node b){

         if(a.x==&&a.y==) return ;

         if(b.x==&&b.y==) return ;

         if(a.x*b.y==a.y*b.x) return a.x<b.x;

         return a.y*b.x<a.x*b.y;

     }

 }a[M];

 set<node> s;

 int n,x,y,m,op[M]={},id[M]={}; bool vis[M]={};

 int cj(node a,node b,node c){return (b-a)*(c-a);}

 double dis(node a,node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

 double ans=;

 void ins(node k){

     set<node>::iterator now,nowm,nown,pre;

     nown=nowm=now=s.upper_bound(k);

     now--; nowm--; nowm--;

     while(cj(*nowm,*now,k)>){

         ans=ans-dis(*nown,*now)-dis(*now,*nowm)+dis(*nown,*nowm);

         pre=now; *now--;

         s.erase(pre);

         if(nowm==s.begin()) break;

         *nowm--;

     }

     if(cj(*now,k,*nown)>) return;

     ans=ans-dis(*nown,*now)+dis(*nown,k)+dis(*now,k);

     s.insert(k);

     nowm=now=nown=s.find(k);

     now++; nown++; nown++;

     while(cj(*nowm,*now,*nown)>&&nown!=s.end()){

         ans=ans-dis(*nown,*now)-dis(*now,*nowm)+dis(*nown,*nowm);

         pre=now; *now++; *nown++;

         s.erase(pre);

     }

 }

 double ansp[M]={};int use=;

 int main(){

     scanf("%d%d%d",&n,&x,&y);

     s.insert(node(,)); s.insert(node(n,)); s.insert(node(x,y));

     ans=dis(node(,),node(x,y))+dis(node(x,y),node(n,));

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);

     scanf("%d",&m);

     for(int i=;i<=m;i++){

         scanf("%d",op+i);

         if(op[i]==) continue;

         scanf("%d",id+i);

         vis[id[i]]=;

     }

     for(int i=;i<=n;i++) if(!vis[i]) ins(a[i]);

     for(int i=m;i;i--){

         if(op[i]==) {ansp[++use]=ans; continue;}

         if(!vis[id[i]]) continue;

         ins(a[id[i]]); vis[id[i]]=;

     }

     while(use) printf("%.2lf\n",ansp[use--]);

 }

巴特西

【BZOJ2300】【HAOI2011】防线修建

最新文章

热门文章