首页 > 代码库 > 【BZOJ】1382: [Baltic2001]Mars Maps (线段树+扫描线)
【BZOJ】1382: [Baltic2001]Mars Maps (线段树+扫描线)
1382: [Baltic2001]Mars Maps
Time Limit: 5 Sec Memory Limit: 64 MBDescription
给出N个矩形,N<=10000.其坐标不超过10^9.求其面积并
Input
先给出一个数字N,代表有N个矩形. 接下来N行,每行四个数,代表矩形的坐标.
Output
输出面积并
Sample Input
2
10 10 20 20
15 15 25 30
10 10 20 20
15 15 25 30
Sample Output
225
本以为是傻逼题,没想到不容易啊~
线段树+扫描线+离散化(也可以不用?!)
如果接触过扫描线,想到解法还比较容易。不过写起来细节重重啊~~~
前几次T掉了,然后调啊调终于A调。。。
虽然A掉了,不过一路坎坷,有些地方改的很玄乎。
还需要好好体会!555
sorry,写的太累,懒得描述了,详见代码吧。。。
#include<iostream>#include<fstream>#include<cstdio>#include<algorithm>#include<string>#include<vector>#include<queue>#include<deque>#include<utility>#include<map>#include<set>#include<cmath>#include<cstdlib>#include<ctime>#include<functional>#include<sstream>#include<cstring>#include<bitset>#include<stack>using namespace std; int n,x1,y1x,x2,y2,ans,cnt;struct sdt{ int l,r,y,flag;}line[500005];int old[500005],lef[500005],rig[500005],sum[500005],cntx[500005],ll[500005],rr[500005]; bool cmp(sdt x,sdt y){ return x.y<y.y;} int read(){ int x=0;char c=getchar(); while(c<48||c>57)c=getchar(); while(c>47&&c<58)x*=10,x+=c-48,c=getchar(); return x;} void check(int x){ if(cntx[x])sum[x]=rr[x]-ll[x]; else if(rig[x]-lef[x]==1)sum[x]=0; else sum[x]=sum[x*2]+sum[x*2+1];} void build(int root,int l,int r){ lef[root]=l; rig[root]=r; ll[root]=old[l]; rr[root]=old[r]; sum[root]=0; cntx[root]=0; if(l+1==r)return ; int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid,r);} void update(int root,sdt x){ if(x.l==ll[root] && x.r==rr[root]) { cntx[root]+=x.flag; check(root); return ; } if(x.l>=ll[root*2+1])update(root*2+1,x); else if(x.r<=rr[root*2])update(root*2,x); else { sdt xx; xx=x; xx.r=rr[root*2]; update(root*2,xx); xx=x; xx.l=ll[root*2+1]; update(root*2+1,xx); } check(root);} int main(){ n=read(); for(int i=1;i<=n;i++) { x1=read(); y1x=read(); x2=read(); y2=read(); line[++cnt].y=y1x; line[cnt].l=x1; line[cnt].r=x2; line[cnt].flag=1; old[cnt]=x1; line[++cnt].y=y2; line[cnt].l=x1; line[cnt].r=x2; line[cnt].flag=-1; old[cnt]=x2; } sort(line+1,line+cnt+1,cmp); sort(old+1,old+cnt+1); build(1,1,cnt); update(1,line[1]); for(int i=2;i<=cnt;i++) { ans+=sum[1]*(line[i].y-line[i-1].y); update(1,line[i]); } printf("%d\n",ans); return 0;}
【BZOJ】1382: [Baltic2001]Mars Maps (线段树+扫描线)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。