Luogu-2521 [HAOI2011]防线修建

倒过来处理所有询问，就变成了一道动态凸包的裸题
吐槽一下这道题只要维护上凸壳就好了，我zz了没好好看题打了两个2333
// luogu-judger-enable-o2

#include<set>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rp (*r)

#define lp (*l)

#define rrp (*rr)

#define llp (*ll)

using namespace std;

const int maxn=1e6+100;

struct Vector{

    double x,y;

    Vector(double xx=0,double yy=0){

        x=xx,y=yy;

    }

};

struct Point{

    double x,y;

    Point(double xx=0,double yy=0){

        x=xx,y=yy;

    }

    bool operator < (Point a) const{

        return x==a.x?y<a.y:x<a.x;

    }

}a[maxn],b[maxn],tmp[maxn];

int dcmp(double x){return fabs(x)<1e-9?0:x>0;}

bool operator == (Point a,Point b){return a.x==b.x&&a.y==b.y;}

Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}

double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}

double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}

double len(Vector a){return sqrt(dot(a,a));}

int m,s,t,ms[maxn],err[maxn],c[maxn],n;

double pp,x,y,ans,an[maxn];

set<Point>u,d;

void tb(Point *p,int &n){

    if(n==1) return;

    sort(p+1,p+n+1);

    tmp[1]=p[1];

    int m=1;

    for(int i=2;i<=n;i++){

        while(m>1&&(tmp[m]-tmp[m-1])*(p[i]-tmp[m-1])<=0)

            m--;

        tmp[++m]=p[i];

    }

    for(int i=1;i<m;i++)

        d.insert(tmp[i]),ans+=len(tmp[i+1]-tmp[i]);

    d.insert(tmp[m]);

    int k=m;

    for(int i=n-1;i>=1;i--){

        while(m>k&&(tmp[m]-tmp[m-1])*(p[i]-tmp[m-1])<=0)

            m--;

        tmp[++m]=p[i];

    }

    for(int i=k;i<m;i++)

        u.insert(tmp[i]),ans+=len(tmp[i+1]-tmp[i]);

    u.insert(tmp[m]);

    ans-=pp;

}

void uinsert(Point p){

    set<Point>::iterator l,r,ll,rr;

    r=u.lower_bound(p);

    l=--r,r++;

//	printf("%lf %lf\n%lf %lf\n",lp.x,lp.y,rp.x,rp.y);

    if((p-lp)*(rp-lp)>0) return;

    ans=ans-len(rp-lp)+len(p-lp)+len(p-rp);

    while(l!=u.begin()){

        ll=--l,l++;

//		printf("%lf %lf\n",llp.x,llp.y);

        if((lp-llp)*(p-llp)<0) break;

//		printf("%lf %lf %lf\n",len(p-lp),len(lp-llp),len(p-llp));

        ans=ans-len(p-lp)-len(lp-llp)+len(p-llp);

        u.erase(l);

        l=ll;

    }

    rr=++r,r--;

    while(rr!=u.end()){

//		printf("%lf %lf\n",rrp.x,rrp.y);

        if((rrp-p)*(rp-p)>0) break;

//		printf("%lf %lf %lf\n",len(rp-p),len(rrp-rp),len(rrp-p));

        ans=ans-len(rp-p)-len(rrp-rp)+len(rrp-p);

        u.erase(r);

        r=rr;

        rr=++r,r--;

    }

    u.insert(p);

}

/*

void dinsert(Point p){

    set<Point>::iterator l,r,ll,rr;

    r=d.lower_bound(p);

    l=--r,r++;

    if((p-lp)*(rp-lp)<0) return;

    ans=ans-len(rp-lp)+len(p-lp)+len(p-rp);

    while(l!=d.begin()){

        ll=--l,l++;

        if((lp-llp)*(p-llp)>0) break;

        ans=ans-len(lp-p)-len(llp-lp)+len(llp-p);

        u.erase(l);

        l=ll;

    }

    rr=++r,r--;

    while(rr!=d.end()){

        if((rrp-p)*(rp-p)>0) break;

        ans=ans-len(rp-p)-len(rrp-rp)+len(rrp-p);

        u.erase(r);

        r=rr;

        rr=++r,r--;

    }

    d.insert(p);

}

*/

int main(){

    scanf("%lf%lf%lf",&pp,&x,&y);

    scanf("%d",&m);

    for(int i=1;i<=m;i++)

        scanf("%lf%lf",&b[i].x,&b[i].y);

    scanf("%d",&t);

    for(int i=1;i<=t;i++){

        scanf("%d",&ms[i]);

        if(ms[i]==1){

            scanf("%d",&c[i]);

            err[c[i]]=1;

        }

    }

    a[1].x=a[1].y=a[2].y=0;

    a[2].x=pp,a[3].x=x,a[3].y=y;

    n=3;

    for(int i=1;i<=m;i++)

        if(!err[i])

            a[++n]=b[i];

    tb(a,n);

    for(int i=t;i>=1;i--){

        if(ms[i]==1)

            uinsert(b[c[i]]);//,dinsert(b[c[i]]);

        else

            an[i]=ans;

    }

    for(int i=1;i<=t;i++)

        if(ms[i]==2)

            printf("%.2lf\n",an[i]);

    return 0;

}
巴特西

Luogu-2521 [HAOI2011]防线修建

最新文章

热门文章
