首页 > 代码库 > sgu Kalevich Strikes Back

sgu Kalevich Strikes Back

这道题就是求一个大矩形被n个矩形划分成n+1个部分的面积,这些矩形之间不会相交,可能包含。。

  1 #include <cstdio>  2 #include <cstring>  3 #include <vector>  4 #include <algorithm>  5 #define maxn 120100  6 using namespace std;  7   8 long long s[maxn];  9 vector<int>g[maxn]; 10 int pre[maxn]; 11 int X[maxn]; 12 int n,m,w,h,x1,y1,x2,y2; 13 struct node 14 { 15     int l,r; 16     int ll,rr; 17     int cover; 18 }tree[maxn*4]; 19  20 struct line 21 { 22     int y,x1,x2,lr; 23     bool operator <(const line &a)const 24     { 25         return y<a.y; 26     } 27 }p[maxn]; 28  29 void build(int i,int l,int r) 30 { 31     tree[i].l=l; 32     tree[i].r=r; 33     tree[i].ll=X[l]; 34     tree[i].rr=X[r]; 35     tree[i].cover=0; 36     if(r-l==1) return ; 37     int mid=(l+r)>>1; 38     build(i<<1,l,mid); 39     build(i<<1|1,mid,r); 40 } 41 void down(int i) 42 { 43     if(tree[i].l+1==tree[i].r) return; 44     if(tree[i].cover!=-1) 45     { 46         tree[i<<1].cover=tree[i<<1|1].cover=tree[i].cover; 47         tree[i].cover=-1; 48     } 49 } 50 void update(int i, line a) 51 { 52     if(tree[i].ll==a.x1&&tree[i].rr==a.x2) 53     { 54         if(a.lr>0) 55             tree[i].cover=a.lr; 56         else 57             tree[i].cover=pre[-a.lr]; 58         return ; 59     } 60     down(i); 61     if(a.x2<=tree[i<<1].rr) update(i<<1,a); 62     else if(a.x1>=tree[i<<1|1].ll) update(i<<1|1,a); 63     else 64     { 65         line tmp=a; 66         tmp.x2=tree[i<<1].rr; 67         update(i<<1,tmp); 68         tmp=a; 69         tmp.x1=tree[i<<1|1].ll; 70         update(i<<1|1,tmp); 71     } 72 } 73  74 int search1(int i,line m) 75 { 76     if(tree[i].cover!=-1) 77     { 78         return tree[i].cover; 79     } 80     if(m.x2<=tree[i<<1].rr) return search1(i<<1,m); 81     else if(m.x1>=tree[i<<1|1].ll) return search1(i<<1|1,m); 82     else 83     { 84         line tmp; 85         tmp=m; 86         tmp.x2=tree[i<<1].rr; 87         return search1(i<<1,tmp); 88     } 89 } 90 void dfs(int u) 91 { 92     for(int i=0; i<(int)g[u].size(); i++) 93     { 94         int v=g[u][i]; 95         s[u]-=s[v]; 96         dfs(v); 97     } 98 } 99 100 int main()101 {102     while(scanf("%d",&n)!=EOF)103     {104         for(int i=0; i<=n; i++)105         {106             g[i].clear();107         }108         scanf("%d%d",&w,&h);109         s[0]=(long long)w*h;110         int t1=0;111         for(int i=1; i<=n; i++)112         {113             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);114             if(x1>x2)swap(x1,x2);115             if(y1>y2)swap(y1,y2);116             s[i]=(long long)(x2-x1)*(y2-y1);117             p[t1].y=y1;118             p[t1].x1=x1;119             p[t1].x2=x2;120             p[t1].lr=i;121             X[t1++]=x1;122             p[t1].y=y2;123             p[t1].x1=x1;124             p[t1].x2=x2;125             p[t1].lr=-i;126             X[t1++]=x2;127         }128         sort(X,X+t1);129         t1=unique(X,X+t1)-X;130         build(1,0,t1-1);131         sort(p,p+2*n);132         for(int i=0; i<2*n; i++)133         {134             if(p[i].lr>0)135             {136                 pre[p[i].lr]=search1(1,p[i]);137                 g[pre[p[i].lr]].push_back(p[i].lr);138             }139             update(1,p[i]);140         }141         dfs(0);142         sort(s,s+n+1);143         for(int i=0; i<=n; i++)144         {145             if(i==n) printf("%I64d\n",s[i]);146             else printf("%I64d ",s[i]);147         }148     }149     return 0;150 }
View Code