【BZOJ 2300】 2300: [HAOI2011]防线修建（动态凸包+set）-白红宇

【BZOJ 2300】 2300: [HAOI2011]防线修建（动态凸包+set）

阅读量：5124 次

发布时间：2019-06-13

本文共 3156 字，大约阅读时间需要 10 分钟。

2300: [HAOI2011]防线修建

Description

近来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)和首都这三个城市是一定需要保护的。

上图中，A,B,C,D,E点为A国城市，且目前都要保护，那么修建的防线就会是A-B-C-D，花费也就是线段AB的长度+线段BC的长度+线段CD的长度,如果，这个时候撤销B点的保护，那么防线变成下图

Input

第一行，三个整数n,x,y分别表示河边城市和首都是(0,0)，(n,0)，(x,y)。

第二行，一个整数m。

接下来m行，每行两个整数a,b表示A国的一个非首都非河边城市的坐标为(a,b)。

再接下来一个整数q，表示修改和询问总数。

接下来q行每行要么形如1 i，要么形如2，分别表示撤销第i个城市的保护和询问。

Output

对于每个询问输出1行，一个实数v，表示修建防线的花费，保留两位小数

Sample Input

4 2 1

2

1 2

3 2

5

2

1 1

2

1 2

2

Sample Output

6.47

5.84

4.47

HINT

m<=100000,q<=200000,n>1

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

Source

【分析】

　　一开始真是想得太少了。

　　这是动态凸包。可以离线，把删除点变成插入点。

　　这题有特殊性，总是有两个城市在河边，一个点是(0,0)，一个点是(n,0)，其余所有点的横坐标均大于0小于n，纵坐标均大于0。

　就是说下凸包是最下面最长的直线，只要维护一个上凸包。

　　（表示还不会真正的动态凸包）

　　这一题只用set维护，就知道插入的点第一个影响的两个点（lower_bound）

　　判断是以x为第一关键字，y为第二关键字。

　　然后不断扩展删点就好了。

　　好难打ORZ,,,竟然1A了。。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 #define Maxn 100010 10 11 struct P 12 { 13 int x,y; 14 }a[Maxn]; 15 int len; 16 17 int m; 18 19 P operator - (P x,P y) 20 { 21 P tt; 22 tt.x=x.x-y.x; 23 tt.y=x.y-y.y; 24 return tt; 25 } 26 27 bool operator < (P x,P y) { return (x.x==y.x)?(x.y
             
              
                t; 33 double ans; 34 35 void ins(P nw) 36 { 37 set
               :: iterator r=t.lower_bound(nw),l=r,tt; 38 l--; 39 if(Cross(nw-*l,*r-*l)>=0) return; 40 ans-=sqrt((double)Dot(*r-*l,*r-*l)); 41 while(1) 42 { 43 tt=r,r++; 44 if(r==t.end()) break; 45 if(Cross(nw-*tt,nw-*r)<=0) break; 46 ans-=sqrt((double)Dot(*r-*tt,*r-*tt)); 47 t.erase(tt); 48 } 49 while(l!=t.begin()) 50 { 51 tt=l,l--; 52 if(Cross(*l-*tt,*l-nw)<=0) break; 53 ans-=sqrt((double)Dot(*l-*tt,*l-*tt)); 54 t.erase(tt); 55 } 56 t.insert(nw); 57 tt=t.find(nw);l=r=tt; 58 l--;r++; 59 ans+=sqrt((double)Dot(nw-*l,nw-*l))+sqrt((double)Dot(nw-*r,nw-*r)); 60 } 61 62 bool mark[Maxn]; 63 int qr[2*Maxn],al; 64 double as[Maxn]; 65 void init() 66 { 67 int n; 68 scanf("%d",&n); 69 a[0].x=0,a[0].y=0;t.insert(a[0]); 70 a[0].x=n,a[0].y=0;t.insert(a[0]); 71 ans=0; 72 scanf("%d%d",&a[0].x,&a[0].y); 73 ans+=n; 74 ins(a[0]); 75 scanf("%d",&m); 76 for(int i=1;i<=m;i++) 77 { 78 scanf("%d%d",&a[i].x,&a[i].y); 79 } 80 81 memset(mark,0,sizeof(mark)); 82 int q; 83 scanf("%d",&q); 84 for(int i=1;i<=q;i++) 85 { 86 int x,y; 87 scanf("%d",&x); 88 if(x==1) 89 { 90 scanf("%d",&y); 91 qr[i]=y; 92 mark[y]=1; 93 } 94 else 95 { 96 qr[i]=-1; 97 } 98 } 99 for(int i=1;i<=m;i++) if(!mark[i]) ins(a[i]);100 al=0;101 for(int i=q;i>=1;i--)102 {103 if(qr[i]==-1)104 {105 as[++al]=ans;106 }107 else108 {109 ins(a[qr[i]]);110 }111 }112 for(int i=al;i>=1;i--) printf("%.2lf\n",as[i]);113 }114 115 int main()116 {117 init();118 return 0;119 }