2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 F题 Overlapping Rectangles（线段树）

127 阅读 0 评论 84 点赞

我是靠谱客的博主踏实唇彩，这篇文章主要介绍2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 F题 Overlapping Rectangles（线段树），现在分享给大家，希望可以做个参考。

求矩阵并集的面积；用线段树来解决

推荐一个线段树求矩阵交并集的思路：

http://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html

客官老爷请移步：

线段树矩阵交并集模板代码：

http://blog.csdn.net/sizaif/article/details/78089278

There are $n$ rectangles on the plane. The problem is to find the area of the union of these rectangles. Note that these rectangles might overlap with each other, and the overlapped areas of these rectangles shall not be counted more than once. For example, given a rectangle $A$ with the bottom left corner located at $(0, 0)$ and the top right corner at $(2, 2)$ , and the other rectangle $B$ with the bottom left corner located at $(1, 1)$ and the top right corner at $(3, 3)$ , it follows that the area of the union of $A$ and $B$ should be $7$ , instead of $8$ .

Although the problem looks simple at the first glance, it might take a while to figure out how to do it correctly. Note that the shape of the union can be very complicated, and the intersected areas can be overlapped by more than two rectangles.

Note:

(1) The coordinates of these rectangles are given in integers. So you do not have to worry about the floating point round-off errors. However, these integers can be as large as $1, 000, 000$ .

(2) To make the problem easier, you do not have to worry about the sum of the areas exceeding the long integer precision. That is, you can assume that the total area does not result in integer overflow.

Input Format

Several sets of rectangles configurations. The inputs are a list of integers. Within each set, the first integer (in a single line) represents the number of rectangles, n, which can be as large as $1000$ . After n, there will be n lines representing the n rectangles; each line contains four integers $< a, b, c, d >$ , which means that the bottom left corner of the rectangle is located at $(a, b)$ , and the top right corner of the rectangle is located at $(c, d)$ . Note that integers $a$ , $b$ , $c$ , $d$ can be as large as $1, 000, 000$ .

These configurations of rectangles occur repetitively in the input as the pattern described above. An integer $n = 0$ (zero) signifies the end of input.

Output Format

For each set of the rectangles configurations appeared in the input, calculate the total area of the union of the rectangles. Again, these rectangles might overlap each other, and the intersecting areas of these rectangles can only be counted once. Output a single star '*' to signify the end of outputs.

样例输入

复制代码

样例输出

复制代码

题目来源

2017 ACM-ICPC 亚洲区（南宁赛区）网络赛

【代码实现】

复制代码

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#define mem(a,b) memset(a,b,sizeof(a))
#define findx(x) lower_bound(b+1,b+1+bn,x)-b
#define FIN
freopen("input.txt","r",stdin)
#define FOUT
freopen("output.txt","w",stdout)
#define S1(n)
scanf("%d",&n)
#define SL1(n)
scanf("%I64d",&n)
#define S2(n,m)
scanf("%d%d",&n,&m)
#define SL2(n,m)
scanf("%I64d%I64d",&n,&m)
#define Pr(n)
printf("%dn",n)
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r
using namespace std;
typedef long long ll;
const double PI=acos(-1);
const int INF=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1e6+5;
const int MAX=50005;
const int MOD=1e9+7;
const int mod=1e9+7;
int dir[5][2]={0,1,0,-1,1,0,-1,0};
ll inv[maxn*2];
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){ x=1; y=0; d=a; }else{ ex_gcd(b,a%b,d,y,x); y-=x*(a/b);};}
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll ans=exgcd(b,a%b,x,y);ll temp=x;x=y;y=temp-a/b*y;return ans;}
ll lcm(ll a,ll b){ return b/gcd(a,b)*a;}
ll qpow(ll x,ll n){ll res=1;for(;n;n>>=1){if(n&1)res=(res*x)%MOD;x=(x*x)%MOD;}return res;}
ll inv_exgcd(ll a,ll n){ll d,x,y;ex_gcd(a,n,d,x,y);return d==1?(x+n)%n:-1;}
ll inv1(ll b){return b==1?1:(MOD-MOD/b)*inv1(MOD%b)%MOD;}
ll inv2(ll b){return qpow(b,MOD-2);}
const int MAXN=2000+5;
int col[MAXN<<2],n,cnt,res;
double X[MAXN<<2],Sum[MAXN<<2],Sum2[MAXN<<2];
struct
Seg{
double l,r,h;
int flag;
Seg(){}
Seg(double l,double r,double h,int flag):l(l),r(r),h(h),flag(flag){}
bool operator <(const Seg & object ) const{
return h<object.h;
}
}S[MAXN<<2];
void pushup(int rt,int l,int r)
{
if(col[rt])//覆盖一次
Sum[rt]=X[r+1]-X[l];
else if(l==r) Sum[rt]=0;
else Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];
if(col[rt]>=2)// 覆盖两次以上
Sum2[rt]=X[r+1]-X[l];
else if(l==r) Sum2[rt]=0;
else if(col[rt]==1) Sum2[rt]=Sum[rt<<1] +Sum[rt<<1|1];
else if(col[rt]==0) Sum2[rt]=Sum2[rt<<1] +Sum2[rt<<1|1];
}
void update(int L,int R,int c,int rt,int l,int r)//
l,r 固定长度 L,R
变化长度
{
if(L<=l&&r<=R)
{
col[rt]+=c;
pushup(rt,l,r);
return;
}
int mid=(l+r)>>1;
if(L<=mid) update(L,R,c,lson);
if(R>mid) update(L,R,c,rson);
pushup(rt,l,r);
}
int binary_find(double x)
{
int lb=-1,ub=res-1;
while(ub-lb>1)
{
int mid=(lb+ub)>>1;
if(X[mid]>=x)ub=mid;
else lb=mid;
}
return ub;
}
double solve(int n)
{
cnt=res=0;
for(int i=0;i<n;i++)
{
double a,b,c,d;
scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
S[cnt]=Seg(a,c,b,1);
X[cnt++]=a;
S[cnt]=Seg(a,c,d,-1);
X[cnt++]=c;
}
sort(X,X+cnt);
sort(S,S+cnt);
res++;
for(int i=1;i<cnt;i++){// 去重
if(X[i]!=X[i-1]) X[res++]=X[i];
}
memset(Sum,0,sizeof(Sum));
memset(col,0,sizeof(col));
memset(Sum2,0,sizeof(Sum2));
double ans=0;
for(int i=0;i<cnt-1;i++)
{
int l=binary_find(S[i].l);//二分左端点，
int r=binary_find(S[i].r)-1; // 左闭右开 二分右端点
update(l,r,S[i].flag,1,0,res-1);
ans+= Sum[1]*(S[i+1].h-S[i].h);// 矩阵并
//ans+= Sum2[1]*(S[i+1].h-S[i].h); //矩阵 交集
}
return ans;
}
int main()
{
while(~scanf("%d",&n))
{
if(n==0)
{
printf("*n");
break;
}
printf("%.lfn",solve(n));
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#define mem(a,b) memset(a,b,sizeof(a))
#define findx(x) lower_bound(b+1,b+1+bn,x)-b
#define FIN
freopen("input.txt","r",stdin)
#define FOUT
freopen("output.txt","w",stdout)
#define S1(n)
scanf("%d",&n)
#define SL1(n)
scanf("%I64d",&n)
#define S2(n,m)
scanf("%d%d",&n,&m)
#define SL2(n,m)
scanf("%I64d%I64d",&n,&m)
#define Pr(n)
printf("%dn",n)
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r
using namespace std;
typedef long long ll;
const double PI=acos(-1);
const int INF=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1e6+5;
const int MAX=50005;
const int MOD=1e9+7;
const int mod=1e9+7;
int dir[5][2]={0,1,0,-1,1,0,-1,0};
ll inv[maxn*2];
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){ x=1; y=0; d=a; }else{ ex_gcd(b,a%b,d,y,x); y-=x*(a/b);};}
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll ans=exgcd(b,a%b,x,y);ll temp=x;x=y;y=temp-a/b*y;return ans;}
ll lcm(ll a,ll b){ return b/gcd(a,b)*a;}
ll qpow(ll x,ll n){ll res=1;for(;n;n>>=1){if(n&1)res=(res*x)%MOD;x=(x*x)%MOD;}return res;}
ll inv_exgcd(ll a,ll n){ll d,x,y;ex_gcd(a,n,d,x,y);return d==1?(x+n)%n:-1;}
ll inv1(ll b){return b==1?1:(MOD-MOD/b)*inv1(MOD%b)%MOD;}
ll inv2(ll b){return qpow(b,MOD-2);}
const int MAXN=2000+5;
int col[MAXN<<2],n,cnt,res;
double X[MAXN<<2],Sum[MAXN<<2],Sum2[MAXN<<2];
struct
Seg{
double l,r,h;
int flag;
Seg(){}
Seg(double l,double r,double h,int flag):l(l),r(r),h(h),flag(flag){}
bool operator <(const Seg & object ) const{
return h<object.h;
}
}S[MAXN<<2];
void pushup(int rt,int l,int r)
{
if(col[rt])//覆盖一次
Sum[rt]=X[r+1]-X[l];
else if(l==r) Sum[rt]=0;
else Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];
if(col[rt]>=2)// 覆盖两次以上
Sum2[rt]=X[r+1]-X[l];
else if(l==r) Sum2[rt]=0;
else if(col[rt]==1) Sum2[rt]=Sum[rt<<1] +Sum[rt<<1|1];
else if(col[rt]==0) Sum2[rt]=Sum2[rt<<1] +Sum2[rt<<1|1];
}
void update(int L,int R,int c,int rt,int l,int r)//
l,r 固定长度 L,R
变化长度
{
if(L<=l&&r<=R)
{
col[rt]+=c;
pushup(rt,l,r);
return;
}
int mid=(l+r)>>1;
if(L<=mid) update(L,R,c,lson);
if(R>mid) update(L,R,c,rson);
pushup(rt,l,r);
}
int binary_find(double x)
{
int lb=-1,ub=res-1;
while(ub-lb>1)
{
int mid=(lb+ub)>>1;
if(X[mid]>=x)ub=mid;
else lb=mid;
}
return ub;
}
double solve(int n)
{
cnt=res=0;
for(int i=0;i<n;i++)
{
double a,b,c,d;
scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
S[cnt]=Seg(a,c,b,1);
X[cnt++]=a;
S[cnt]=Seg(a,c,d,-1);
X[cnt++]=c;
}
sort(X,X+cnt);
sort(S,S+cnt);
res++;
for(int i=1;i<cnt;i++){// 去重
if(X[i]!=X[i-1]) X[res++]=X[i];
}
memset(Sum,0,sizeof(Sum));
memset(col,0,sizeof(col));
memset(Sum2,0,sizeof(Sum2));
double ans=0;
for(int i=0;i<cnt-1;i++)
{
int l=binary_find(S[i].l);//二分左端点，
int r=binary_find(S[i].r)-1; // 左闭右开 二分右端点
update(l,r,S[i].flag,1,0,res-1);
ans+= Sum[1]*(S[i+1].h-S[i].h);// 矩阵并
//ans+= Sum2[1]*(S[i+1].h-S[i].h); //矩阵 交集
}
return ans;
}
int main()
{
while(~scanf("%d",&n))
{
if(n==0)
{
printf("*n");
break;
}
printf("%.lfn",solve(n));
}
return 0;
}