当前位置：首页 > news >正文

P1884 [USACO12FEB] Overplanting S

news 2026/6/12 21:45:02

传送门

题目描述

在一个笛卡尔平面坐标系里（则X XX轴向右是正方向，Y YY轴向上是正方向），有N ( 1 ≤ N ≤ 1000 ) N\ (1 \le N \le 1000)N(1≤N≤1000)个矩形，第i ii个矩形的左上角坐标是( x 1 , y 1 ) (x_1,y_1)(x1,y1)，右下角坐标是( x 2 , y 2 ) (x_2,y_2)(x2,y2)。问这N NN个矩形所覆盖的面积是多少？

注意：被重复覆盖的区域的面积只算一次。

输入格式

第一行，一个整数N ( 1 ≤ N ≤ 1000 ) N\ (1 \le N \le 1000)N(1≤N≤1000)。

接下来有N NN行，每行描述一个矩形的信息，分别是矩形的x 1 , y 1 , x 2 , y 2 ( − 10 8 ≤ x 1 , y 1 , x 2 , y 2 ≤ 10 8 ) x_1,y_1,x_2,y_2(-10^8 \le x_1,y_1,x_2,y_2 \le 10^8)x1,y1,x2,y2(−108≤x1,y1,x2,y2≤108)。

输出格式

一个整数，被N NN个矩形覆盖的区域的面积。

输入输出样例 #1

输入 #1

2 0 5 4 1 2 4 6 2

输出 #1

思路

本题为扫描线模板题，可左转学习。

但此题与模板不同，有一坑点：它给出的左下角的y 1 y1y1有可能比右下角的y 2 y2y2大，所以遇到这种情况需要交换y 1 y1y1和y 2 y2y2。

代码

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongstructdid{intl,r,lc,rc,tag,c;}tr[400001];structline{inty1,y2,x,f;}l[200001];boolcmp(line a,line b){returna.x<b.x;}intn,y[200001],tot;longlongans;voidbuild(intl,intr){tot++;intp=tot;tr[p].l=l,tr[p].r=r,tr[p].lc=tr[p].rc=-1,tr[p].c=tr[p].tag=0;if(l==r)return;intmid=(l+r)>>1;tr[p].lc=tot+1;build(l,mid);tr[p].rc=tot+1;build(mid+1,r);}voidpushup(intl,intr,intp){if(tr[p].tag==0){if(l==r)tr[p].c=0;elsetr[p].c=tr[tr[p].lc].c+tr[tr[p].rc].c;}}voidchange(intl,intr,intc,intp){if(tr[p].l>=l&&tr[p].r<=r){tr[p].tag+=c;if(tr[p].tag)tr[p].c=y[tr[p].r+1]-y[tr[p].l];elsetr[p].c=0;pushup(tr[p].l,tr[p].r,p);return;}intmid=(tr[p].l+tr[p].r)>>1;if(r<=mid)change(l,r,c,tr[p].lc);elseif(l>mid)change(l,r,c,tr[p].rc);elsechange(l,mid,c,tr[p].lc),change(mid+1,r,c,tr[p].rc);pushup(tr[p].l,tr[p].r,p);}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(inti=1;i<=n;i++){intx1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;if(y1>y2)swap(y1,y2);y[(i<<1)-1]=y1;y[i<<1]=y2;l[(i<<1)-1]=(line){y1,y2,x1,1};l[i<<1]=(line){y1,y2,x2,-1};}n<<=1;sort(y+1,y+1+n);sort(l+1,l+1+n,cmp);intcnt=unique(y+1,y+1+n)-(&y[1])-1;build(1,cnt);for(inti=1;i<n;i++){inty1=lower_bound(y+1,y+cnt+2,l[i].y1)-y;inty2=lower_bound(y+1,y+cnt+2,l[i].y2)-y-1;change(y1,y2,l[i].f,1);ans+=tr[1].c*(l[i+1].x-l[i].x);}cout<<ans;return0;}