P1884 [USACO12FEB] Overplanting S

传送门题目描述在一个笛卡尔平面坐标系里则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输入 #12 0 5 4 1 2 4 6 2输出 #120思路本题为扫描线模板题可左转学习。但此题与模板不同有一坑点它给出的左下角的y 1 y1y1有可能比右下角的y 2 y2y2大所以遇到这种情况需要交换y 1 y1y1和y 2 y2y2。代码#includebits/stdc.husingnamespacestd;#defineintlonglongstructdid{intl,r,lc,rc,tag,c;}tr[400001];structline{inty1,y2,x,f;}l[200001];boolcmp(line a,line b){returna.xb.x;}intn,y[200001],tot;longlongans;voidbuild(intl,intr){tot;intptot;tr[p].ll,tr[p].rr,tr[p].lctr[p].rc-1,tr[p].ctr[p].tag0;if(lr)return;intmid(lr)1;tr[p].lctot1;build(l,mid);tr[p].rctot1;build(mid1,r);}voidpushup(intl,intr,intp){if(tr[p].tag0){if(lr)tr[p].c0;elsetr[p].ctr[tr[p].lc].ctr[tr[p].rc].c;}}voidchange(intl,intr,intc,intp){if(tr[p].lltr[p].rr){tr[p].tagc;if(tr[p].tag)tr[p].cy[tr[p].r1]-y[tr[p].l];elsetr[p].c0;pushup(tr[p].l,tr[p].r,p);return;}intmid(tr[p].ltr[p].r)1;if(rmid)change(l,r,c,tr[p].lc);elseif(lmid)change(l,r,c,tr[p].rc);elsechange(l,mid,c,tr[p].lc),change(mid1,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);cinn;for(inti1;in;i){intx1,y1,x2,y2;cinx1y1x2y2;if(y1y2)swap(y1,y2);y[(i1)-1]y1;y[i1]y2;l[(i1)-1](line){y1,y2,x1,1};l[i1](line){y1,y2,x2,-1};}n1;sort(y1,y1n);sort(l1,l1n,cmp);intcntunique(y1,y1n)-(y[1])-1;build(1,cnt);for(inti1;in;i){inty1lower_bound(y1,ycnt2,l[i].y1)-y;inty2lower_bound(y1,ycnt2,l[i].y2)-y-1;change(y1,y2,l[i].f,1);anstr[1].c*(l[i1].x-l[i].x);}coutans;return0;}