the input consists of several test cases. each test case starts with a line containing a single integer n (1 <= n <= 100) of available maps. the n following lines describe one map each. each of these lines contains four numbers x1;y1;x2;y2 (0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000), not necessarily integers. the values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
the input file is terminated by a line containing a single 0. don't process it.
1000000000.
for
each test case, your program should output one section. the first line
of each section must be "test case #k", where k is the number of the
test case (starting with 1). the second one must be "total explored
area: a", where a is the total explored area (i.e. the area of the union
of all rectangles in this test case), printed exact to two digits to
the right of the decimal point.
output a blank line after each test case.
1 //#include<bits/stdc++.h>
2 #include<cstdio>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 #define n 10050
7 int n,cnt,tot,cas;
8 double kth[n];
9 struct query
10 {
11 double l,r,h; int id;
12 bool operator <(const query&b)const
13 {return h<b.h;}
14 }que[n<<1];
15 struct tree{int l,r,lazy;double sum;}tr[n<<2];
16 template<typename t>void read(t&x)
17 {
18 int k=0;char c=getchar();
19 x=0;
20 while(!isdigit(c)&&c!=eof)k^=c=='-',c=getchar();
21 if(c==eof)exit(0);
22 while(isdigit(c))x=x*10+c-'0',c=getchar();
23 x=k?-x:x;
24 }
25 void push_up(int x)
26 {
27 double len=(kth[tr[x].r]-kth[tr[x].l]);
28 tr[x].sum=0;
29 if (tr[x].lazy>0)tr[x].sum=len;
30 else if(tr[x].r-tr[x].l>1)tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
31 }
32 void bt(int x,int l,int r)
33 {
34 tr[x]=tree{l,r,0,0};
35 if(r-l==1)return;
36 int mid=(l+r)>>1;
37 bt(x<<1,l,mid);
38 bt(x<<1|1,mid,r);
39 }
40 void update(int x,int l,int r,int tt)
41 {
42 if (l<=tr[x].l&&tr[x].r<=r)
43 {
44 tr[x].lazy+=tt;
45 push_up(x);
46 return;
47 }
48 int mid=(tr[x].l+tr[x].r)>>1;
49 if(l<mid)update(x<<1,l,r,tt);
50 if(mid<r)update(x<<1|1,l,r,tt);
51 push_up(x);
52 }
53 double query(int x,int l,int r)
54 {
55 if (l<=tr[x].l&&tr[x].r<=r) return tr[x].sum;
56 int mid=(tr[x].l+tr[x].r)>>1;
57 double ans=0;
58 if(l<mid)ans+=query(x<<1,l,r);
59 if(mid<r)ans+=query(x<<1|1,l,r);
60 return ans;
61 }
62 void input()
63 {
64 read(n);
65 if (n==0)exit(0);
66 double x1,y1,x2,y2;
67 for(int i=1;i<=n;i++)
68 {
69 //read(x1);read(y1); read(x2);read(y2);
70 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
71 que[++tot]=query{x1,x2,y1,1};
72 que[++tot]=query{x1,x2,y2,-1};
73 kth[++cnt]=x1;kth[++cnt]=y1;
74 kth[++cnt]=x2;kth[++cnt]=y2;
75 }
76 }
77 void work()
78 {
79 double ans=0;
80 sort(que+1,que+tot+1);
81 sort(kth+1,kth+cnt+1);
82 cnt=unique(kth+1,kth+cnt+1)-kth-1;
83 bt(1,1,cnt);
84 for(int i=1;i<=tot-1;i++)
85 {
86 int l=lower_bound(kth+1,kth+cnt+1,que[i].l)-kth;
87 int r=lower_bound(kth+1,kth+cnt+1,que[i].r)-kth;
88 update(1,l,r,que[i].id);
89 ans+=tr[1].sum*(que[i+1].h-que[i].h);
90 }
91 //printf("test case #%d\ntotal explored area: %.2lf\n\n",++cas,ans);
92 printf("test case #%d\n", ++cas);
93 printf("total explored area: %.2f\n\n", ans);
94 }
95 void clear(){cnt=0;tot=0;}
96 int main()
97 {
98 #ifndef online_judge
99 freopen("aa.in","r",stdin);
100 #endif
101 while(1)
102 {
103 clear();
104 input();
105 work();
106 }
107 }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!!
点击进行留言回复
网友评论