POJ 1389. Area of Simple Polygons 题解

关于扫描线的介绍可以去看 OI Wiki。

但那上面的参考代码并不好，下面给出了带注释的 POJ 1389 题代码。

/*
 * Title: Area of Simple Polygons
 * Source: POJ
 * URL: http://poj.org/problem?id=1389
 * Author: Steven_lzx
 * Command: -std=c++23 -Wall -fno-ms-extensions
 * Date: 2022.10.19
 */
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=2005,MAXM=200005;
struct Rec
{
    int x1,x2,y,w;
    bool operator <(Rec b)const{return y<b.y;}
}p[2005];
int tree[MAXM],lazy[MAXM];
void build(int p,int l,int r)
{
    int mid;
    lazy[p]=0;
    if(l==r)
    {
        tree[p]=0;
        return;
    }
    mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tree[p]=tree[p<<1]+tree[p<<1|1];
    return;
}
void update(int p,int l,int r,const int L,const int R,int c)
{
    int mid;
    if(R<l||L>r)
        return;
    if(L<=l&&r<=R)
    {
        lazy[p]+=c;
        if(lazy[p]>0)
            tree[p]=r-l+1;//完全覆盖，值为区间长
        else if(l==r)
            tree[p]=0;//该点没有被覆盖，清零
        else 
            tree[p]=tree[p<<1]+tree[p<<1|1];//没有被完全覆盖，需要重新更新 
        return;
    }
    mid=(l+r)>>1;
    update(p<<1,l,mid,L,R,c);
    update(p<<1|1,mid+1,r,L,R,c);
    if(!lazy[p])
        tree[p]=tree[p<<1]+tree[p<<1|1];//没有被完全覆盖，需要重新更新
    return;
}
int main()
{
    int n,a,b,c,d;
    ll h,ans;
    bool over=false;
    while(true)
    {
        n=0;
        while(true)
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            if(!~a&&!~b&&!~c&&!~d)
            {
                if(!n)
                    over=true;
                break;
            }
            n++;
            p[n*2].x1=p[n*2-1].x1=a;
            p[n*2-1].y=b;
            p[n*2].x2=p[n*2-1].x2=c;
            p[n*2].y=d;
            p[n*2-1].w=1;
            p[n*2].w=-1;
        }
        if(over)
            break;
        sort(p+1,p+(n<<1)+1);
        build(1,0,5e4);
        ans=0;
        update(1,0,5e4,p[1].x1+1,p[1].x2,p[1].w);//建一个底
        for(int i=2;i<=n<<1;i++)//因为是点数和，所有求长度的话要减去一个点就为长度
        {
            h=p[i].y-p[i-1].y;
            ans+=h*tree[1];//底乘高
            update(1,0,5e4,p[i].x1+1,p[i].x2,p[i].w);
        }
        printf("%lld\n",ans);
    }
    return 0;
}