★★★☆?? 輸入文件：defense.in?? 輸出文件：defense.out???簡單對比
　　　　　　　　　　　　　　　　　　　　　　時間限制：1 s?? 內存限制：128 MB

題目描述：

近來A國和B國的矛盾激化，為了預防不測，A國準備修建一條長長的防線，當然修建防線的話，肯定要把需要保護的城市修在防線內部了。可是A國上層現在還猶豫不決，到底該把哪些城市作為保護對象呢？又由于A國的經費有限，所以希望你能幫忙完成如下的一個任務：

給出你所有的A國城市坐標

A國上層經過討論，考慮到經濟問題，決定取消對i城市的保護，也就是說i城市不需要在防線內了

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點的保護，那么防線變成下圖

?

輸入格式：

第一行，三個整數n,x,y分別表示河邊城市和首都是(0,0)，(n,0)，(x,y)。

第二行，一個整數m。

接下來m行，每行兩個整數a,b表示A國的一個非首都非河邊城市的坐標為(a,b)。

再接下來一個整數q，表示修改和詢問總數。

接下來q行每行要么形如1 i，要么形如2，分別表示撤銷第i個城市的保護和詢問。

輸出格式：

對于每個詢問輸出1行，一個實數v，表示修建防線的花費，保留兩位小數

樣例輸入：

4 2 1

2

1 2

3 2

5

2

1 1

2

1 2

2

樣例輸出：

6.47

5.84

4.47

數據范圍：

30%的數據m<=1000,q<=1000

100%的數據m<=100000,q<=200000,n>1

所有點的坐標范圍均在10000以內,?數據保證沒有重點

題解：

　　此題要求動態地去維護一個凸包的周長，我們可以發現，要想從凸包上刪除一個點然后更新答案并不容易，因為凸包內部的點的信息不好維護，不妨把所有操作先存下來，離線反向操作。每碰到一個操作1，添加一個點，添加點無非是看這個點是在凸包的內部還是外部，內部的就不用管了，對答案并沒有什么卵用，如果是在外部，就看在這個點左邊的凸包上的點和右邊凸包上的點會不會被覆蓋，這個用向量的叉積判斷即可

1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 #include<cstring> 7 #include<queue> 8 #include<cstring> 9 #include<set> 10 using namespace std; 11 const double eps=1e-7; 12 int n,x,y,m,q; 13 double now; 14 struct Q{ 15 int kin,i; 16 double ans; 17 }opt[300000]; 18 bool vis[200000]; 19 struct P{ 20 int x,y; 21 }p[200005],del[200005]; 22 inline P operator-(P a,P b){ 23 P t; t.x=a.x-b.x; t.y=a.y-b.y; 24 return t; 25 } 26 inline double operator*(P a,P b){ 27 return a.x*b.y-b.x*a.y; 28 } 29 inline bool operator<(P a,P b){ 30 if(a.x==b.x) return a.y<b.y; 31 return a.x<b.x; 32 } 33 inline double dis(P a,P b){ 34 return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))); 35 } 36 37 set<P> A; 38 inline void insert(int a,int b){ 39 P x=(P){a,b}; 40 set<P>::iterator r=A.lower_bound(x),l=r,t; 41 l--; 42 if((*l-x)*(*r-x)<0) return ; 43 now-=dis(*l,*r); 44 A.insert(x); 45 while(r!=A.end()){ 46 t=r; r++; 47 if((*r-x)*(*t-x)>0) break; 48 now-=dis(*t,*r); 49 A.erase(t); 50 } 51 while(l!=A.begin()){ 52 t=l; l--; 53 if((*t-x)*(*l-x)>0) break; 54 now-=dis(*t,*l); 55 A.erase(t); 56 } 57 A.insert(x); 58 l=r=t=A.find(x); 59 l--; r++; 60 now+=dis(*l,x)+dis(*r,x); 61 } 62 63 int main(){ 64 // freopen("defense.in","r",stdin); 65 // freopen("defense.out","w",stdout); 66 scanf("%d%d%d",&n,&x,&y); 67 scanf("%d",&m); 68 for(int i=1;i<=m;i++) scanf("%d%d",&p[i].x,&p[i].y); 69 scanf("%d",&q); 70 for(int i=1;i<=q;i++){ 71 scanf("%d",&opt[i].kin); 72 if(opt[i].kin==1){ 73 scanf("%d",&opt[i].i); 74 vis[opt[i].i]=true; 75 } 76 } 77 P cap; cap.x=x; cap.y=y; 78 now+=dis((P){0,0},cap); now+=dis((P){n,0},cap); 79 A.insert((P){0,0}); A.insert((P){n,0}); A.insert((P){x,y}); 80 for(int i=1;i<=m;i++){ 81 if(vis[i]==false) insert(p[i].x,p[i].y); 82 } 83 for(int i=q;i>=1;i--){ 84 if(opt[i].kin==2){ 85 opt[i].ans=now; 86 } 87 else{ 88 insert(p[opt[i].i].x,p[opt[i].i].y); 89 } 90 } 91 for(int i=1;i<=q;i++){ 92 if(opt[i].kin==2){ 93 printf("%.2lf\n",opt[i].ans); 94 } 95 } 96 return 0; 97 }

?

轉載于:https://www.cnblogs.com/CXCXCXC/p/5246619.html

總結

以上是生活随笔為你收集整理的cogs 547:[HAOI2011] 防线修建的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。