JSOI2012-夏令营 Mar Maps

浏览数：42 / 时间：2015年06月09日

火星探险

源程序名 　　　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

10 10 20 20

15 15 25 30

MAR.OUT

又见模板题 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].mid
14 #define len(i) T[i].r-T[i].l
15 #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); else
43         if(l==r-1)     T[i].len = 0;      else
44                        T[i].len = T[Ch1].len + T[Ch2].len;
45         return;
46     }
47     if(r<=mid(i))  Modify(l,r,delta,Ch1);else
48     if(l>=mid(i))  Modify(l,r,delta,Ch2);else
49     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 }