首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。