覆盖的面积
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3353 Accepted Submission(s): 1638
Problem Description
给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
Input
输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.
注意:本题的输入数据较多,推荐使用scanf读入数据.
Output
对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.
Sample Input
2 5 1 1 4 2 1 3 3 7 2 1.5 5 4.5 3.5 1.25 7.5 4 6 3 10 7 3 0 0 1 1 1 0 2 1 2 0 3 1
Sample Output
7.63 0.00
Author
Ignatius.L & weigang Lee
传送门：【HDU】1255 覆盖的面积
题目分析：
求矩阵面积交。
once[]表示区间覆盖一次或以上的长度。
more[]表示区间覆盖两次或以上的长度。
如果当前区间被覆盖两次或以上，则once[]和more[]等同，可以直接用自己的信息更新自己。
如果当前区间被覆盖一次或以上，则once[]可以用自己的信息更新自己，more用子节点的once[]更新自己。
如果当前区间没有覆盖标记，则once[]用子节点的once[]更新自己，more[]用子节点的more[]更新自己。
传递思想与求矩阵面积并类似，而且最后本题的once[]就是矩阵面积并。
PS：写完后，答案和样例一直对不上，查了很久的错，很多地方输出了中间结果，发现就more[]得到的值特别奇怪，然后顺着这里找啊找，找到了二分查找里面，看着看着很正常啊没什么不对的。。。。。后来再次查到二分的时候突然发现。。。。没有加else导致l一直增大。。。改了以后，样例对上了，也直接AC了T T。真是苦
代码如下：
#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 = 2048 ;
const double eps = 1e-6 ;
struct Line {
double l , r , h ;
int f ;
Line () {}
Line ( double L , double R , double H , int F ) : l(L) , r(R) , h(H) , f(F) {}
bool operator < ( const Line &L ) const {
return h < L.h ;
}
} ;
Line line[maxN] ;
int cover[maxN << 2] ;
double a[maxN] ;
double once[maxN << 2] , more[maxN << 2] ;
int sgn ( double x ) {
return ( x > eps ) - ( x < -eps ) ;
}
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 = 1 ;
sort ( a + 1 , a + n + 1 ) ;
for ( int i = 2 ; i <= n ; ++ i ) {
if ( sgn ( a[i] - a[cnt] ) ) a[++ cnt] = a[i] ;
}
return cnt ;
}
void PushUp ( int o , int l , int r ) {
if ( cover[o] >= 2 ) {
more[o] = once[o] = a[r + 1] - a[l] ;
}
else if ( cover[o] == 1 ) {
once[o] = a[r + 1] - a[l] ;
if ( l == r ) more[o] = 0 ;
else more[o] = once[ls] + once[rs] ;
}
else {
if ( l == r ) more[o] = once[o] = 0 ;
else{
once[o] = once[ls] + once[rs] ;
more[o] = more[ls] + more[rs] ;
}
}
}
void Update ( int L , int R , int v , int o , int l , int r ) {
if ( L <= l && r <= R ) {
cover[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 ) ;
}
void work () {
int n , cnt = 0 , __cnt = 0 ;
double x1 , x2 , y1 , y2 ;
clear ( once , 0 ) ;
clear ( more , 0 ) ;
clear ( cover , 0 ) ;
scanf ( "%d" , &n ) ;
for ( int i = 0 ; i < n ; ++ i ) {
scanf ( "%lf%lf%lf%lf" , &x1 , &y1 , &x2 , &y2 ) ;
line[++ __cnt] = Line ( x1 , x2 , y1 , 1 ) ;
line[++ __cnt] = Line ( x1 , x2 , y2 , -1 ) ;
a[++ cnt] = x1 ;
a[++ cnt] = x2 ;
}
cnt = Unique ( a , cnt ) ;
/*
printf ( "cnt = %d\n" , cnt ) ;
for ( int i = 1 ; i <= cnt ; ++ i ) printf ( "a[%d] = %.2f\n" , i , a[i] ) ;
*/
n = __cnt ;
sort ( line + 1 , line + n + 1 ) ;
double area = 0 ;
for ( int i = 1 ; i < n ; ++ i ) {
int L = Search ( line[i].l , 1 , cnt + 1 ) ;
int R = Search ( line[i].r , 1 , cnt + 1 ) ;
Update ( L , R - 1 , line[i].f , 1 , 1 , cnt - 1 ) ;
area += ( line[i + 1].h - line[i].h ) * more[1] ;
}
printf ( "%.2f\n" , area ) ;
}
int main () {
int T ;
scanf ( "%d" , &T ) ;
while ( T -- ) work () ;
return 0 ;
}