覆盖的面积

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 4040 Accepted Submission(s): 1995

Problem Description

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

Input

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N& lt;=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 

      交G++迷之WA。。无语 

      C++可过。 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          using namespace std;#define root 1,(n<<1)+10,1#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define lr rt<<1#define rr rt<<1|1const int N = 4010 ;struct Point {    double x , y1 , y2 ;    int v ;    bool operator < ( const Point &a ) const {        return x < a.x ;    }}p[N];int n , tot , tt ;vector
           
            e;double c[N<<2] ;void addpoint( double x , double y1 , double y2 , int v ) { p[tot].x = x , p[tot].y1 = y1 , p[tot].y2 = y2 , p[tot].v = v , tot++ ;}map
            
             mp;void lisan() { mp.clear(); sort( e.begin() , e.end() ) ; tt = 1 ; for( int i = 1 ; i < e.size() ; ++i ) { if( e[i] != e[i-1] ) e[tt++] = e[i] ; } for( int i = 0 ; i < tt ; ++i ) { c[i+1] = e[i] ; mp[e[i]] = i+1 ; }}int cnt[N<<2] , lazy[N<<2] ;double date[N<<2] ;void build( int l , int r , int rt ) { cnt[rt] = lazy[rt] = 0 ; if( l == r ) { date[rt] = c[l+1] - c[l]; return ; } int mid = (l+r)>>1; build(lson) , build(rson) ; date[rt] = date[lr] + date[rr];}void Down( int rt ) { if( lazy[rt] ) { cnt[lr] += lazy[rt] ; cnt[rr] += lazy[rt] ; lazy[lr] += lazy[rt] ; lazy[rr] += lazy[rt] ; lazy[rt] = 0 ; }}void Up( int rt ) { cnt[rt] = min( cnt[lr] , cnt[rr] );}void update( int l , int r , int rt , int L , int R , int v ) { if( l == L && r == R ) { cnt[rt] += v ; lazy[rt] += v ; return ; } int mid = (l+r)>>1 ; Down(rt) ; if( R <= mid ) update(lson,L,R,v) ; else if( L > mid ) update( rson,L,R,v); else update(lson,L,mid,v),update(rson,mid+1,R,v); Up(rt);}double query( int l , int r , int rt , int L , int R ) { if( cnt[rt] > 1 ) return date[rt] ; if( l == r ) return 0 ; Down(rt); int mid = (l+r)>>1; if( R <= mid ) return query(lson,L,R); else if( L > mid ) return query(rson,L,R); else return query(lson,L,mid) + query(rson,mid+1,R);}int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int _ ; scanf("%d",&_); while( _-- ) { scanf("%d",&n); e.clear(); tot = 0 ; for( int i = 0 ; i < n ; ++i ) { double x1 , y1 , x2 , y2 ; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); if( y1 > y2 ) swap( y1 , y2 ) ; addpoint( x1 , y1 , y2 , 1 ); addpoint( x2 , y1 , y2 , -1 ); e.push_back(y1); e.push_back(y2); } lisan(); sort( p , p + tot ) ; build(1,tt-1,1); double ans = 0 ; update(1,tt-1,1,mp[p[0].y1],mp[p[0].y2]-1,p[0].v); for( int i = 1 ; i < tot ; ++i ) { ans += ( p[i].x - p[i-1].x ) * query(1,tt-1,1,1,tt-1) ; update(1,tt-1,1,mp[p[i].y1],mp[p[i].y2]-1,p[i].v); } printf("%.2lf\n",ans); } return 0 ;}

View Code

转载于:https://www.cnblogs.com/hlmark/p/4366818.html

你可能感兴趣的文章

洛谷 P1313 计算系数 Label：杨辉三角形多项式计算