http://acm.pku.edu.cn/JudgeOnline/problem?id=1151
//离散化 + 线段树 + 扫描线
//本题与poj 1177 picture 极相似
//与 1177 不同的是本题中的坐标是浮点
//类型的故不能将坐标直接离散.我们必须为它们建立一个对应关系,用一个整数去对应一个浮点数
1
#include<iostream>
2#include<algorithm>
3#define MAXN 205
4using namespace std;
5
6struct line
7
{
8
double x;
9 double y1,y2;
10 int flag;
11 bool operator<( const line &a )
12
{
13 return x<a.x;
14
}
15
};
16
17struct segment_tree
18{
19 int L,R;
20 double len;
21 int cover;
22};
23
24struct point
25{
26 double y;
27 int num;
28 bool operator<( const point &a )
29 {
30 return y<a.y;
31 }
32};
33segment_tree tree[MAXN*4];
34point Xpoint[MAXN],Ypoint[MAXN];
35line yline[MAXN];
36int Xpost[MAXN][2],Ypost[MAXN][2];
37
38void make_tree( int v, int l, int r )
39{
40 int mid;
41 tree[v].L=l;
42 tree[v].R=r;
43 tree[v].len=0;
44 tree[v].cover=0;
45 if( r-l>1 )
46 {
47 mid=( l+r )>>1;
48 make_tree( v<<1, l, mid );
49 make_tree( (v<<1)+1, mid, r );
50 }
51}
52
53void getlen( int v )
54{
55 if( tree[v].cover>0 )
56 tree[v].len=Ypoint[tree[v].R].y-Ypoint[tree[v].L].y;
57 else if( tree[v].R-tree[v].L==1 )
58 tree[v].len=0;
59 else tree[v].len=tree[v<<1].len+tree[(v<<1)+1].len;
60}
61
62void update( int v, int l, int r, int flag )
63{
64 int mid;
65 if( tree[v].L==l && tree[v].R==r )
66 {
67 tree[v].cover+=flag;
68 getlen( v );
69 return ;
70 }
71 mid=( tree[v].L+tree[v].R )>>1;
72 if( mid>=r ) update( v<<1, l, r, flag );
73 else if( mid<=l )update( (v<<1)+1, l, r, flag );
74 else
75 {
76 update( v<<1, l, mid, flag );
77 update( (v<<1)+1, mid, r, flag );
78 }
79 getlen( v );
80}
81
82int main( )
83{
84 int n,i,t1,t2,cas=0;
85 double x1,x2,y1,y2;
86 while( scanf("%d",&n) && n )
87 {
88 for( i=0; i<n; i++ )
89 {
90 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
91 t1=i<<1;t2=(i<<1)+1;
92 yline[t1].x=x1,yline[t2].x=x2;
93 yline[t1].flag=1;yline[t2].flag=-1;
94 Ypoint[t1].y=y1;Ypoint[t2].y=y2;
95 Ypoint[t1].num=-(i+1);Ypoint[t2].num=i+1;
96 Xpoint[t1].y=x1;Xpoint[t2].y=x2;
97 Xpoint[t1].num=-(i+1);Xpoint[t2].num=i+1;
98 }
99 sort( Xpoint, Xpoint+(n<<1) );
100 sort( Ypoint, Ypoint+(n<<1) );
101 sort( yline, yline+(n<<1) );
102 for( i=0; i<(n<<1); i++ )
103 {
104 if( Xpoint[i].num<0 )Xpost[-Xpoint[i].num-1][0]=i;
105 else Xpost[Xpoint[i].num-1][1]=i;
106 }
107 for( i=0; i<(n<<1); i++ )
108 {
109 if( Ypoint[i].num<0 )
110 Ypost[Xpost[-Ypoint[i].num-1][0]][0]=Ypost[Xpost[-Ypoint[i].num-1][1]][0]=i;
111 else Ypost[Xpost[Ypoint[i].num-1][0]][1]=Ypost[Xpost[Ypoint[i].num-1][1]][1]=i;
112 }
113 make_tree( 1, 0, (n<<1)-1 );
114 double ans=0;
115 update( 1, Ypost[0][0], Ypost[0][1], yline[0].flag );
116 for( i=1; i<(n<<1); i++ )
117 {
118 ans+=tree[1].len*( yline[i].x-yline[i-1].x);
119 update( 1, Ypost[i][0], Ypost[i][1], yline[i].flag );
120 }
121 printf("Test case #%d\nTotal explored area: %.2lf\n\n",++cas,ans);
122 }
123 return 0;
124}
125