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
2Sample Output
6.47
5.84
4.47HINT
m<=100000,q<=200000,n>1
所有点的坐标范围均在10000以内, 数据保证没有重点Source
【分析】
一开始真是想得太少了。
这是动态凸包。可以离线，把删除点变成插入点。
这题有特殊性，总是有两个城市在河边，一个点是(0,0)，一个点是(n,0)，其余所有点的横坐标均大于0小于n，纵坐标均大于0。
就是说下凸包是最下面最长的直线，只要维护一个上凸包。
（表示还不会真正的动态凸包）
这一题只用set维护，就知道插入的点第一个影响的两个点（lower_bound）
判断是以x为第一关键字，y为第二关键字。
然后不断扩展删点就好了。
好难打ORZ,,,竟然1A了。。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<cmath> 7 #include<set> 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<y.y):(x.x<y.x);} 28 29 int Dot(P x,P y) {return x.x*y.x+x.y*y.y;} 30 int Cross(P x,P y) {return x.x*y.y-x.y*y.x;} 31 32 set<P> t; 33 double ans; 34 35 void ins(P nw) 36 { 37 set<P>:: 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 else 108 { 109 ins(a[qr[i]]); 110 } 111 } 112 for(int i=al;i>=1;i--) printf("%.2lf ",as[i]); 113 } 114 115 int main() 116 { 117 init(); 118 return 0; 119 }
2016-12-17 10:07:03