题解 P2521 【[HAOI2011]防线修建】

rhjoi · 2019-08-05 08:26:23 · 题解

SOL

题意：离线询问，维护动态凸包，支持加点，查询凸包周长。

用set，按x坐标排序，先判断是否在凸包内，再用双向迭代器向两边枚举删点即可。

具体实现参照代码。

//set很够用了，可能不会再手写平衡树来维护动态凸包了。 //代码有所借鉴某大佬

CODE

#include<bits/stdc++.h>
#define pf printf
#define sf scanf
#define cs const
#define ll long long
#define db double
#define int long long
using namespace std;
cs int N=1e6+10;
cs db eps=1e-7,inf=1e18,pi=acos(-1);
struct Vector {
    int x,y;
    Vector (int x=0,int y=0):x(x),y(y){}
    friend Vector operator +(cs Vector &a,cs Vector &b){return Vector(a.x+b.x,a.y+b.y);}
    friend Vector operator -(cs Vector &a,cs Vector &b){return Vector(a.x-b.x,a.y-b.y);}
    friend int operator *(cs Vector &a,cs Vector &b){return a.x*b.y-a.y*b.x;}
    bool operator <(cs Vector &t)cs{
        return x==t.x? y<t.y:x<t.x;
        //注意双关键字排序维护凸包
    }
}p[N],cp;

set<Vector>S;
db now;
inline db lenth(cs Vector &a){
    return sqrt(a.x*a.x+a.y*a.y);
}
inline void insert(cs Vector &x){
    set<Vector>:: iterator r=S.lower_bound(x),l=r,t;
    --l;
    if((*l-x)*(*r-x)<0)return;
    now-=lenth(*r-*l);
    while(r!=S.end()){
        t=r;++r;
        if(r==S.end()||(*r-x)*(*t-x)>0)break;
        now-=lenth(*r-*t);
        S.erase(t);
    }
    while(l!=S.begin()){
        t=l;--l;
        if((*l-x)*(*t-x)<0)break;
        now-=lenth(*l-*t);
        S.erase(t);
    }   
    S.insert(x);
    l=r=S.find(x);
    --l;++r;
    now+=lenth(x-*l)+lenth(x-*r);
}
struct node{
    int kd,id;
    db ans;
}q[N];
int n,m,Q;
bool vis[N];
signed main(){
    sf("%d%d%d",&n,&cp.x,&cp.y);
    sf("%d",&m);
    for(int i=1;i<=m;++i)sf("%d%d",&p[i].x,&p[i].y);
    sf("%d",&Q);
    for(int i=1;i<=Q;++i){
        sf("%d",&q[i].kd);
        if(q[i].kd==1)sf("%d",&q[i].id),vis[q[i].id]=1;
    }
    S.insert(Vector(0,0));
    S.insert(Vector(n,0));
    S.insert(cp);
    now=lenth(cp)+lenth(Vector(n,0)-cp);
    for(int i=1;i<=m;++i)if(!vis[i])insert(p[i]);
    for(int i=Q;i>=1;--i){
        if(q[i].kd==2)q[i].ans=now;
        else insert(p[q[i].id]);
    }
    for(int i=1;i<=Q;++i)if(q[i].kd==2)pf("%.2lf\n",q[i].ans);

    return 0;   
}