首页 > 代码库 > JSOI2012-夏令营 Mar Maps

JSOI2012-夏令营 Mar Maps

2024-07-10 01:44:52   222人阅读

火星探险

源程序名 　　　MAR.??? (PAS,C,CPP)

输入文件名　　 MAR.IN

输出文件名     MAR.OUT

时间限制      1S

 

问题描述：

在2051年，若干火星探险队探索了这颗红色行星的不同的区域并且制作了这些区域的地图。现在, Baltic空间机构有一个雄心勃勃的计划：他们想制作一张整个行星的地图。为了考虑必要的工作，他们需要知道地图上已经存在的全部区域的大小。你的任务是写一个计算这个区域大小的程序。

 

任务：

l         从输入文件 mar.in 读取地图形状的描述

l         计算地图覆盖的全部的区域

l         输出到输出文件mar.out

 

输入：

输入文件mar.in的第一行包含一个整数N(1<=N<=10000)，表示可得到的地图数目。

以下N行，每行描述一张地图。

每行包含4个整数x1，y1，x2和y2(0<=x1<x2<=30000，0<=y1<y2<=30 000)。数值(x1，y1)和(x2，y2)是坐标，分别表示绘制区域的左上角和右下角坐标。每张地图是矩形的，并且它的边是平行与X坐标轴或Y坐标轴的。

 

输出：

输出文件 mar.out，应该包含一个整数，表示探索区域的总面积(即所有矩形的公共面积)。

 

样例：

MAR.IN

2
10 10 20 20
15 15 25 30

 

MAR.OUT

225

又见模板题  T_T。。没办法就是这么水。。

不过是第一次学习扫描线统计周长面积什么的

 

Codes:

 1 #include<set> 2 #include<queue> 3 #include<vector> 4 #include<cstdio> 5 #include<cstdlib> 6 #include<cstring> 7 #include<iostream> 8 #include<algorithm> 9 using namespace std;10 const int N = 30010;11 #define Ch1 (i<<1)12 #define Ch2 (Ch1|1)13 #define mid(i) T[i].mid14 #define len(i) T[i].r-T[i].l15 #define For(i,n) for(int i=1;i<=n;i++)16 #define Rep(i,l,r) for(int i=l;i<=r;i++)17 18 struct lines{19     int l,r,h,kind;20 }L[N];21 22 struct tnode{23     int l,r,mid;24     int cover,len;25 }T[N<<2];26 27 int n,tot,x1,y1,x2,y2,Lim,ans;28 29 bool cmp(lines A,lines B){30     return A.h<B.h;31 }32 33 void Build(int l,int r,int i){34     T[i].l = l; T[i].r = r; T[i].mid = (l+r)>>1;35     if(l==r-1) return;36     Build(l,mid(i),Ch1);Build(mid(i),r,Ch2);37 }38 39 void Modify(int l,int r,int delta,int i){40     if(l<=T[i].l&&T[i].r<=r){41         T[i].cover+=delta;42         if(T[i].cover) T[i].len = len(i); else43         if(l==r-1)     T[i].len = 0;      else44                        T[i].len = T[Ch1].len + T[Ch2].len;45         return;46     }47     if(r<=mid(i))  Modify(l,r,delta,Ch1);else48     if(l>=mid(i))  Modify(l,r,delta,Ch2);else49     Modify(l,mid(i),delta,Ch1),Modify(mid(i),r,delta,Ch2);50     if(T[i].cover) T[i].len = len(i); 51     else           T[i].len = T[Ch1].len + T[Ch2].len;52 }53 54 void init(){55     scanf("%d",&n);56     For(i,n){57         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);58         L[++tot].l = x1; L[tot].r = x2; L[tot].h = y1;L[tot].kind = 0;59         L[++tot].l = x1; L[tot].r = x2; L[tot].h = y2;L[tot].kind = 1;60         Lim = max(Lim,x2);61     }62     sort(L+1,L+tot+1,cmp);63     Build(0,Lim,1);L[0].h = L[1].h;64 }65 66 int main(){67     freopen("mar.in","r",stdin);68     freopen("mar.out","w",stdout);69     init();70     For(i,tot){71         if(!L[i].kind){72             ans+=T[1].len*(L[i].h-L[i-1].h);73             Modify(L[i].l,L[i].r,1,1);74         }else{75             ans+=T[1].len*(L[i].h-L[i-1].h);76             Modify(L[i].l,L[i].r,-1,1);77         }78     }79     cout<<ans<<endl;80     return 0;81 }

 

 

 


联系
我们