動態(tài)加點維護凸包。

論STL的熟練運用。

#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<iostream> #include<string> #include<map> #include<set> #include<cstdlib> #include<cmath> #include<iomanip> using namespace std; #define LL long long #define FILE "dealing" #define eps 1e-10 #define db double #define up(i,j,n) for(int i=j;i<=n;i++) int read(){int x=0,f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f; } const int maxn=101000,mod=1000000007,inf=10000000000000LL; bool cmin(int& a,int b){return a>b?a=b,true:false;} bool cmax(int& a,int b){return a<b?a=b,true:false;} int n,m; db s,t; int ch[maxn],p[maxn],b[maxn],q; int dcmp(db a){if(fabs(a)<eps)return 0;return a<0?-1:1;} struct vec{db x,y,l,r;vec(db x=0,db y=0,db l=0,db r=0):x(x),y(y),l(l),r(r){} }a[maxn]; bool operator<(vec a,vec b){return dcmp(a.x-b.x)<0||(!dcmp(a.x-b.x)&&a.y<b.y);} bool operator==(vec a,vec b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);} vec operator+(vec b,vec a){return vec(b.x+a.x,b.y+a.y);} vec operator-(vec b,vec a){return vec(b.x-a.x,b.y-a.y);} set<vec> d; set<vec>::iterator it,pre,rev; db qik(vec a,vec b){return (b.y-a.y)/(b.x-a.x);} db dot(vec a,vec b){return a.x*b.x+a.y*b.y;} db len(vec a){return sqrt(dot(a,a));} db ans=0; db y[maxn]; void insert(vec a){d.insert(a);it=d.find(a);pre=--it;it++;rev=++it;it--;db k=qik(*pre,*rev);db b=pre->y-pre->x*k;db y=k*a.x+b;if(dcmp(y-a.y)>0){d.erase(it);return;}ans-=(rev->l);while(dcmp(len(*rev-vec(n,0)))){//printf("%.2lf %.2lf %.2lf %.2lf\n",it->x,it->y,it->l,it->r);vec b=*rev,c=*(++rev);if(dcmp(qik(a,b)-qik(b,c))<0){rev--;ans-=rev->r;d.erase(rev);rev=++it;it--;}else break;}while(dcmp(len(*pre-vec(0,0)))){vec b=*pre,c=*(--pre);if(dcmp(qik(c,b)-qik(b,a))<0){pre++;ans-=pre->l;d.erase(pre);pre=--it;it++;}else break;}it=d.find(a);pre=--it;it++;rev=++it;it--;vec w=*it,qian=*pre,hou=*rev;ans+=(qian.r=w.l=len(*it-*pre));ans+=(hou.l=w.r=len(*rev-*it));d.erase(it);d.erase(pre);d.erase(rev);d.insert(w);d.insert(qian);d.insert(hou);it=d.begin();//for(;it!=d.end();it++)printf("%.2lf %.2lf %.2lf %.2lf\n",it->x,it->y,it->l,it->r);//cout<<endl;//cout<<ans<<endl; } void init(){n=read(),s=read(),t=read();m=read();ans=n;up(i,1,m)a[i].x=read(),a[i].y=read();q=read();up(i,1,q){ch[i]=read();if(ch[i]==1)p[i]=read(),b[p[i]]=1;}d.insert(vec(0,0,0,n));d.insert(vec(n,0,n,0));insert(vec(s,t));up(i,1,m)if(!b[i])insert(a[i]);for(int i=q;i>=1;i--){if(ch[i]==1)insert(a[p[i]]);else y[i]=ans;}up(i,1,q)if(ch[i]==2)printf("%.2lf\n",y[i]); } int main(){//freopen(FILE".in","r",stdin);//freopen(FILE".out","w",stdout);init();return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/chadinblog/p/6441596.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。