程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3265(矩形面積並-分割矩形)

HDU 3265(矩形面積並-分割矩形)

編輯:C++入門知識

Posters
Problem Description
有很多海報,每個海報都被減去了一個矩形(可能全減),現在給出沒張海報的位置,求它們的面積並。
保證坐標在(0, 0)到(50000, 50000)之間。沒有海報斜著貼,減去的矩形邊與x,y軸平行。
 
Input
有很多數據。
對於每組數據第一行有一個整數N (0<N<=50000)表示海報數 接下來n行,每行8個整數 x1, y1, x2, y2, x3, y3, x4, y4, 表示每張海報的左下角坐標(x1, y1),右上角坐標(x2, y2) ,減去的矩形左上角坐標(x3, y3),右上角坐標(x4, y4)(0<=xi, yi<=50000(i=1…4) and x1<=x3<x4<=x2, y1<=y3<y4<=y2).

數據以0結尾。
 

Output
對於每組數據輸出一行,表示它們的面積並。
 

Sample Input
2
0 0 10 10 1 1 9 9
2 2 8 8 3 3 7 7
0
 

Sample Output
56
 
這題就是要把矩形差分成如下形式:


然後進行矩形面積並:
謹記問題轉化後各數組的大小。

[cpp] 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
#include<cmath> 
#include<cctype> 
#include<iostream> 
#include<functional> 
#include<algorithm> 
using namespace std; 
#define MAXN (50000+10) 
#define MAXT (MAXN*5) 
#define MAXXi (50000+10) 
#define Lson (x<<1) 
#define Rson ((x<<1)^1) 
int hpos[MAXN]; 
int x[MAXN*4]={0}; 
struct SegMent 

    int x1,x2,h,type; 
    SegMent(){} 
    SegMent(int _x1,int _x2,int _h,int _type):x1(_x1),x2(_x2),h(_h),type(_type){} 
    friend bool operator<(const SegMent a,const SegMent b){return a.h<b.h;}    
}; 
int n,size; 
struct SegMent_array 

    SegMent a[MAXN*8]; 
    int size; 
    SegMent_array():size(0) 
    { 
        memset(a,0,sizeof(a)); 
    }    
              
    bool add(int x1,int x2,int y1,int y2) 
    { 
        if (x1==x2||y1==y2) return 0; 
        else 
        { 
            a[++size]=SegMent(x1,x2,y1,1); 
            a[++size]=SegMent(x1,x2,y2,-1); 
            return 1; 
        } 
    }    
}a; 
struct SegMentTree 

    long long sum[MAXT],cnt[MAXT],len[MAXT]; 
    int M,n; 
    void fillchar(int _n) 
    { 
        n=_n; 
        M=1;while (M-2<n) M<<=1; 
        memset(sum,0,sizeof(sum)); 
        memset(cnt,0,sizeof(cnt)); 
        memset(len,0,sizeof(len));         
        for (int i=M+1;i<=M+n;i++) len[i]=x[i-M+1]-x[i-M]; 
        for (int i=M-1;i>=1;i--) len[i]=len[i<<1]+len[(i<<1)^1]; 
    } 
    void pushup(int x) 
    { 
        sum[x]=(cnt[x])?(len[x]):((x<M)?(sum[Lson]+sum[Rson]):0); 
    } 
    void update(int x) 
    { 
        while (x) 
        { 
            pushup(x);x>>=1; 
        } 
    } 
    void insert(int l,int r,long long c) 
    { 
        if (l>r) return ; 
        l=l-1+M;r=r+1+M; 
        int ll=l,rr=r; 
        for (;l^r^1;l>>=1,r>>=1) 
        { 
            if (~l&1) {cnt[l+1]+=c; pushup(l+1);} 
            if (r&1) {cnt[r-1]+=c; pushup(r-1);} 
        } 
//      cout<<endl<<"Push:"<<ll<<' '<<rr<<endl; 
        update(ll);update(rr);       
    } 
    void print() 
    { 
        for (int i=1;i<=2*M;i++) if (sum[i]) cout<<i<<':'<<sum[i]<<' '; 
        cout<<endl; 
        for (int i=1;i<=2*M;i++) if (cnt[i]) cout<<i<<':'<<cnt[i]<<' '; 
        cout<<endl; 
        cout<<endl; 
    }       
}t; 
  
  
int main() 

//  freopen("Hdu3265.in","r",stdin); 
    while (scanf("%d",&n)!=EOF) 
    { 
        if (n==0) break; 
        for (int i=1;i<=n;i++) 
        { 
            int x1,y1,x2,y2,x3,y3,x4,y4; 
            scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4); 
            a.add(x1,x3,y1,y4); 
            a.add(x3,x2,y1,y3); 
            a.add(x1,x4,y4,y2); 
            a.add(x4,x2,y3,y2); 
            x[i*4-3]=x1;x[i*4-2]=x2;x[i*4-1]=x3;x[i*4]=x4;  
        } 
        sort(x+1,x+4*n+1); 
        size=unique(x+1,x+4*n+1)-(x+1); 
/*      for (int i=1;i<=size;i++) cout<<x[i]<<' ';
        cout<<endl;
*/     
//      cout<<size; 
        for (int i=1;i<=size;i++) hpos[x[i]]=i; 
        t.fillchar(size-1); 
     
        sort(a.a+1,a.a+1+a.size); 
//      cout<<'s'; 
//      for (int i=1;i<=a.size;i++) cout<<a.a[i].x1<<' '<<a.a[i].x2<<' '<<a.a[i].h<<' '<<a.a[i].type<<endl; 
        long long ans=0; 
        for (int i=1;i<=a.size;i++) 
        { 
            ans+=t.sum[1]*((long long)a.a[i].h-a.a[i-1].h); 
            t.insert(hpos[a.a[i].x1],hpos[a.a[i].x2]-1,a.a[i].type);     
/*          cout<<a.a[i].x1<<' '<<a.a[i].x2<<' '<<a.a[i].h<<' '<<a.a[i].type<<endl;
            cout<<ans<<endl;
            t.print();
*/      } 
        cout<<ans<<endl; 
        a.size=0; 
    } 
    return 0; 

 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved