首页 > 代码库 > 【BZOJ】1382: [Baltic2001]Mars Maps (线段树+扫描线)

【BZOJ】1382: [Baltic2001]Mars Maps (线段树+扫描线)

1382: [Baltic2001]Mars Maps

Time Limit: 5 Sec  Memory Limit: 64 MB

Description

给出N个矩形,N<=10000.其坐标不超过10^9.求其面积并

Input

先给出一个数字N,代表有N个矩形. 接下来N行,每行四个数,代表矩形的坐标.

Output

输出面积并

Sample Input

2
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 (线段树+扫描线)