Atlantis
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6356 Accepted Submission(s): 2798
regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.
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.
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.
2 10 10 20 20 15 15 25 25.5 0
Test case #1 Total explored area: 180.00
题目大意：给你n(n <= 100)个矩阵，问你矩阵并后的面积。
题目分析：
矩阵面积并。
这就是一题最基本的线段树+扫描线。趁此机会学习了一下基本的扫描线。
对于扫描线什么的解释我就不说了，不会的去网上找资料。
这里说一下自己的一些理解：
每次标记覆盖的时候，我们用cov = 1表示这是一条矩阵的下边，cov = -1表示这是上边，更新的时候扫描线从下到上，所以对于相同位置一定是先加后减。
为什么扫描线不需要向下传递标记？按照我的理解是：
1.如果该线段已经被标记完全覆盖，那么自己就用自己的信息更新自己，且向上更新的时候直接上传自己的信息就行了，没必要用到子节点的信息。
2.如果没有被标记且还有子节点存在，那么本节点的信息就需要从子节点上传了。
等等！我们好像没有下传标记吧？那么信息从何而来？
假设本节点属于的区间和另一个区间在X轴上的投影产生交集的时候，那么要么该节点被标记了两次（完全被两个区间包含），要么该节点的子节点被标记（该节点被一个区间包含，被另一个区间不完全包含）。那么在取走该区间上的标记后导致该节点无标记的时候，其子节点可能还存在标记，也就是说该区间还有部分被覆盖！那么，我们就用子节点的信息来更新自己的信息。
间接的我们可以得到一个信息，由于同样长度同样位置（X轴相同）的线段必定是成对出现（矩阵的下边和上边），则标记放置必定对应着标记收回，且该线段的标记对其他线段标记不会产生影响。由于这样的特性以及没有查询的存在的情况下，我们用不到标记下传，所以，当本节点没有被标记且存在子节点的时候，通过子节点的信息更新自己即可。
3.如果没有被标记，并且本节点是叶子节点，那么必定长度是0了。
现在的理解只能达到这种浅显的层面吧，希望以后能有更深的认识
。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define rt o , l , r
#define root 1 , 1 , n
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define clear( A , X ) memset ( A , X , sizeof A )
const int maxN = 100005 ;
const int maxM = 105 ;
const double eps = 1e-6 ;
struct Seg {
double l , r , h ;
int f ;
Seg () {}
Seg ( double L , double R , double H , int F ) : l(L) , r(R) , h(H) , f(F) {}
bool operator < ( const Seg &S ) const {
return h < S.h ;
}
} ;
Seg seg[maxM << 1] ;
int cov[maxN << 2] ;
double sum[maxN << 2] ;
double a[maxM << 1] ;
int sgn ( double x ) {
return ( x > eps ) - ( x < -eps ) ;
}
void PushUp ( int o , int l , int r ) {
if ( cov[o] ) sum[o] = a[r + 1] - a[l] ;//如果本节点被完全覆盖，直接用本节点的信息去更新
else if ( l == r ) sum[o] = 0 ;//如果本节点是叶子节点且没被覆盖，必定是0
else sum[o] = sum[ls] + sum[rs] ;//否则通过子节点的信息更新自己，因为可能有两条线段在X轴上的映射产生交集（即重叠），那么拿去一条线段，则覆盖长度还可能通过子节点（其他线段在子节点上留下的信息）上传。
}
void Update ( int L , int R , int v , int o , int l , int r ) {
if ( L <= l && r <= R ) {
cov[o] += v ;
PushUp ( rt ) ;
return ;
}
int m = mid ;
if ( L <= m ) Update ( L , R , v , lson ) ;
if ( m < R ) Update ( L , R , v , rson ) ;
PushUp ( rt ) ;
}
int search ( double x , int l , int r ) {//二分查找
while ( l < r ) {
int m = mid ;
if ( sgn ( a[m] - x ) >= 0 ) r = m ;
else l = m + 1 ;
}
return l ;
}
int Unique ( double *a , int n ) {//离散化
int cnt = 0 ;
sort ( a , a + n ) ;
for ( int i = 1 ; i < n ; ++ i )
if ( sgn ( a[i] - a[cnt] ) )
a[++ cnt] = a[i] ;
return cnt + 1 ;
}
void work () {
int n , cnt , cas = 0 ;
double x1 , y1 , x2 , y2 ;
while ( ~scanf ( "%d" , &n ) && n ) {
clear ( sum , 0 ) ;
clear ( cov , 0 ) ;
cnt = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
scanf ( "%lf%lf%lf%lf" , &x1 , &y1 , &x2 , &y2 ) ;
seg[i << 1 ] = Seg ( x1 , x2 , y1 , 1 ) ;
seg[i << 1 | 1] = Seg ( x1 , x2 , y2 , -1 ) ;
a[cnt ++] = x1 ;
a[cnt ++] = x2 ;
}
n <<= 1 ;
cnt = Unique ( a , cnt ) ;//离散化
sort ( seg , seg + n ) ;
double area = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
int l = search ( seg[i].l , 0 , cnt ) , r = search ( seg[i].r , 0 , cnt ) ;
Update ( l , r - 1 , seg[i].f , 1 , 0 , cnt - 2 ) ;
area += ( seg[i + 1].h - seg[i].h ) * sum[1] ;
}
printf ( "Test case #%d\n" , ++ cas ) ;
printf ( "Total explored area: %.2f\n\n" , area ) ;
}
}
int main () {
work () ;
return 0 ;
}