//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "防线修建": {
        "prefix": "acm-8.3动态凸包 维护周长",
        "body": [
            "#include<algorithm>",
            "#include<cstdio>",
            "#include<queue>",
            "#include<cmath>",
            "#include<set>",
            "#define LD double",
            "#define LL long long",
            "#define Vector Point",
            "#define Re register int",
            "using namespace std;",
            "const int N=1e5+3;",
            "const LD eps=1e-8,Pi=acos(-1.0);",
            "inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}",
            "inline LD Abs(LD a){return a*dcmp(a);}",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "struct Point{",
            "    LL x,y;Point(LL X=0,LL Y=0){x=X,y=Y;}",
            "    inline void In(){Re X,Y;in(X),in(Y),x=X,y=Y;}",
            "    inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}",
            "};",
            "inline LL Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}",
            "inline LL Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}",
            "inline LD Len(Vector a){return sqrt((LD)Dot(a,a));}",
            "inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}",
            "inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}",
            "inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}",
            "inline bool operator==(Vector a,Vector b){return a.x==b.x&&a.y==b.y;}",
            "struct Splay{",
            "\t#define pl tr[p].ps[0]",
            "\t#define pr tr[p].ps[1]",
            "\t#define pf tr[p].fa",
            "\t#define pv tr[p].v",
            "\tint O,root;queue<int>Q;LD ans;",
            "\tstruct QAQ{int fa,ps[2];Point v;}tr[N];",
            "\tinline int which(Re p){return tr[pf].ps[1]==p;}",
            "\tinline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}",
            "\tinline void rotate(Re p){",
            "\t\tRe fa=pf,fas=which(p);",
            "\t\tRe pa=tr[fa].fa,pas=which(fa);",
            "\t\tRe x=tr[p].ps[fas^1];",
            "\t\tconnect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);",
            "\t}",
            "\tinline void splay(Re p){",
            "\t\tfor(Re fa;pf;rotate(p))",
            "\t\t\tif(tr[fa=pf].fa)rotate(which(p)==which(fa)?fa:p);",
            "\t\troot=p;",
            "\t}",
            "\tinline void CL(Re p){tr[p].v=Point(),pf=pl=pr=0,p=0;}",
            "\tinline int New(){",
            "\t\tRe p;",
            "\t\tif(Q.empty())p=++O;",
            "\t\telse p=Q.front(),Q.pop();",
            "\t\treturn p;",
            "\t}",
            "\tinline void del(Re p){CL(p),Q.push(p);}",
            "\tinline int pre(Re p){p=pl;while(pr)p=pr;return p;}",
            "\tinline int nex(Re p){p=pr;while(pl)p=pl;return p;}",
            "\tinline void insert(Point v){",
            "\t\tRe p=root,fa=0;",
            "\t\twhile(p)fa=p,p=tr[p].ps[!(pv<v)];",
            "\t\tp=New(),pv=v,pf=fa;",
            "\t\tif(fa)tr[fa].ps[!(tr[fa].v<v)]=p;",
            "\t\tsplay(p);Re p1=0,p2=0;",
            "\t\tif(pl)p1=pre(p);if(pr)p2=nex(p);",
            "\t\tif(p1&&p2)ans-=Len(tr[p2].v-tr[p1].v);",
            "\t\tif(p1)ans+=Len(v-tr[p1].v);",
            "\t\tif(p2)ans+=Len(v-tr[p2].v);",
            "\t}",
            "\tinline void erase(Point v){",
            "\t\tRe p=root;",
            "\t\twhile(!(pv==v))p,p=tr[p].ps[!(pv<v)];",
            "\t\tsplay(p);",
            "\t\tRe p1=0,p2=0;",
            "\t\tif(pl)p1=pre(p);if(pr)p2=nex(p);",
            "\t\tif(p1&&p2)ans+=Len(tr[p2].v-tr[p1].v);",
            "\t\tif(p1)ans-=Len(v-tr[p1].v);",
            "\t\tif(p2)ans-=Len(v-tr[p2].v);",
            "\t\tif(!pl&&!pr){root=0,del(p);return;}",
            "\t\tif(!pl||!pr){tr[root=pl+pr].fa=0,del(p);return;}",
            "\t\tsplay(pre(p)),tr[root].ps[1]=pr,tr[pr].fa=root,del(p);",
            "\t}",
            "};",
            "#define IT set<Point>::iterator",
            "struct ConvexHull{",
            "\tint op;set<Point>s;LD ans;//Splay ss;",
            "\tinline void Insert(Point P){",
            "\t\ts.insert(P);IT p=s.find(P);",
            "\t\tRe o1=0,o2=0;IT p1=p,p2=p;",
            "\t\tif(p1!=s.begin())o1=1,--p1;if(++p2!=s.end())o2=1;",
            "\t\tif(o1&&o2)ans-=Len(*p2-*p1);",
            "\t\tif(o1)ans+=Len(*p-*p1);",
            "\t\tif(o2)ans+=Len(*p-*p2);",
            "\t}",
            "\tinline void Erase(IT p){",
            "\t\tRe o1=0,o2=0;IT p1=p,p2=p;",
            "\t\tif(p1!=s.begin())o1=1,--p1;if(++p2!=s.end())o2=1;",
            "\t\tif(o1&&o2)ans+=Len(*p2-*p1);",
            "\t\tif(o1)ans-=Len(*p-*p1);",
            "\t\tif(o2)ans-=Len(*p-*p2);",
            "\t\ts.erase(p);",
            "\t}",
            "\tinline int PIP(Point P){",
            "\t\tIT it=s.lower_bound(Point(P.x,-2e9));",
            "\t\tif(it==s.end())return 0;",
            "\t\tif(it->x==P.x)return (P.y-it->y)*op<=0;",
            "\t\tif(it==s.begin())return 0;",
            "\t\tIT j=it,k=it;--j;return Cro(P-*j,*k-*j)*op>=0;",
            "\t}",
            "\tinline int judge(IT it){",
            "\t\tIT j=it,k=it;",
            "\t\tif(j==s.begin())return 0;--j;",
            "\t\tif(++k==s.end())return 0;",
            "\t\treturn Cro(*it-*j,*k-*j)*op>=0;",
            "\t}",
            "\tinline void insert(Point P){",
            "\t\tif(PIP(P))return;",
            "\t\tIT tmp=s.lower_bound(Point(P.x,-2e9));if(tmp!=s.end()&&tmp->x==P.x)Erase(tmp);//ss.erase(*tmp),s.erase(tmp);",
            "\t\tInsert(P);/*s.insert(P),ss.insert(P);*/IT it=s.find(P),p=it;",
            "\t\tif(p!=s.begin()){--p;while(judge(p)){IT tmp=p--;Erase(tmp);/*ss.erase(*tmp),s.erase(tmp);*/}}",
            "\t\tif((p=++it)!=s.end())while(judge(p)){IT tmp=p++;Erase(tmp);/*ss.erase(*tmp),s.erase(tmp);*/}",
            "\t}",
            "}up,down;",
            "int n,x,T,X[N],op[N],vis[N];LD Ans[N];Point P[N];",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(x),P[0].In(),up.op=1,down.op=-1;",
            "\tup.insert(P[0]),down.insert(P[0]);",
            "\tup.insert(Point(0,0)),down.insert(Point(0,0));",
            "\tup.insert(Point(x,0)),down.insert(Point(x,0));",
            "\tin(n);for(Re i=1;i<=n;++i)P[i].In();",
            "\tin(T);for(Re i=1;i<=T;++i){in(op[i]);if(op[i]<2)in(x),vis[X[i]=x]=1;}",
            "\tfor(Re i=1;i<=n;++i)if(!vis[i])up.insert(P[i]),down.insert(P[i]);",
            "\tfor(Re i=T;i>=1;--i)",
            "\t\tif(op[i]<2)up.insert(P[X[i]]),down.insert(P[X[i]]);",
            "\t\telse Ans[i]=up.ans+Len(*up.s.begin()-*down.s.begin())+Len(*--up.s.end()-*--down.s.end());",
            "\tfor(Re i=1;i<=T;++i)if(op[i]>1)printf(\"%.2lf\\n\",Ans[i]);",
            "}",
            ""
        ],
        "description": "插入 防线修建"
    }
}