扫描线

本文主要是介绍扫描线，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
const int maxn=1e6+10;
ll tree[maxn<<2];
ll lz[maxn<<2];
ll x[maxn<<1];
struct Line {
    int flag;
    long long l, r, h;
    Line(): l(), r(), h(), flag() {}
    Line(long long _l, long long _r, long long _h, int _flag): l(_l), r(_r), h(_h), flag(_flag) {}
    bool operator < (const Line& rhs) const {
        return h < rhs.h;
    }
} line[2 * maxn];
void pushup(int l,int r,int rt){
    if(lz[rt]){
        tree[rt]=(x[r+1]-x[l]);
    }
    else
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
} 
//void pushdown(int l,int r,int rt){
//    if(lz[rt]){
//        int m=(l+r)>>1;
//        lz[rt<<1]+=lz[rt];
//        lz[rt<<1|1]+=lz[rt];
//        pushup(lson);
//        pushup(rson);
//        lz[rt]=0;
//    }
//}
void update_range(int L,int R,ll add,int l,int r,int rt){
    //cout<<L<<" "<<R<<endl;
    //cout<<l<<" "<<r<<" "<<x[r]<<endl;
    if (x[r+1] <= L || x[l]>=R) {
        return;
    }
    if(x[l]>=L&&x[r+1]<=R){
        lz[rt]+=add;
        pushup(l,r,rt);
        return ;
    }
    //pushdown(l,r,rt);
    int m=(l+r)>>1;
    if(L<=x[m])update_range(L,R,add,lson);
    if(R>x[m])update_range(L,R,add,rson);
    pushup(l,r,rt);
}
//ll query_range(int L,int R,int l,int r,int rt){
//    if (x[r+1] <= L || x[l]>= R) {
//        return 0;
//    }
//    if(x[l]>=L&&R>=x[r+1]){
//        pushup(l,r,rt);
//        return tree[rt];
//    }
//    pushdown(l,r,rt);
//    int m=(l+r)>>1;
//    ll sum=0;
//    if(L<=x[m])sum+=query_range(L,R,lson);
//    if(R>x[m])sum+=query_range(L,R,rson);
//    return sum;
//}
void solve(){
    ll ans=0;
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++){
        ll x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        x[2*i-1]=x1;
        x[2*i]=x2;
        line[2*i-1]=Line(x1,x2,y1,1);
        line[2*i]=Line(x1,x2,y2,-1);
    }    
    n*=2;
    sort(line+1,line+n+1);
    sort(x+1,x+n+1);
    ll m=unique(x+1,x+1+n)-x-1;
    for(int i=1;i<n;i++){
        update_range(line[i].l,line[i].r,line[i].flag,1,m-1,1);
        //cout<<line[i].flag<<endl;
        ans+=(tree[1]*(line[i + 1].h - line[i].h));
    //    cout<<tree[1]<<endl;
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
//    getlist(1e7);
    int t=1;
//    cin>>t;
    while(t--){
        solve();
    }
}

这篇关于扫描线的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！