扫描线

我们通过扫描矩形的边(长或者宽),维护两边并集,来计算面积/周长并。
这样定义矩形的边

1
2
3
4
5
6
7
8
struct Edge{
int x,y1,y2;
int in; // 1 入边 -1 出边
Edge(int x,int y1,int y2,int in):x(x),y1(y1),y2(y2),in(in) {}
bool operator<(const Edge& rhs) const{
return x < rhs.x;
}
};

大多时候需要离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<Edge> save;
vector<int> point;

{
scanf("%d",&n);
for(int i=0;i<n;++i)
{
int x1,y1,x2,y2; // (x1,y1) < (x2,y2)
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
save.push_back(Edge(x1,y1,y2,1));
save.push_back(Edge(x2,y1,y2,-1));
point.push_back(y1); point.push_back(y2);
}

sort(save.begin(),save.end());
sort(point.begin(),point.end());
int pn = unique(point.begin(),point.end()) - point.begin();
}

线段树维护并集

我们加一个cnt标记,表示整个区间被覆盖的次数。
每次pushup的时候,当前区间被标记,则说明当前区间应被全部填满。
因为这里只需要查找整个区间,所以可以不写query函数

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
struct Node{
int cnt,len,num; //len 并集长度 num 并集个数
bool l,r; //左右端点标记
Node() { cnt = len = num = l = r = 0;}
} p[maxn<<3];

void pushup(int L,int R,int u)
{
if(p[u].cnt)
{
p[u].len = point[R+1] - point[L];
p[u].l = p[u].r = 1;
p[u].num = 1;
}
else if(L == R)
{
p[u].len = p[u].num = p[u].l = p[u].r = 0;
}
else
{
p[u].len = p[u<<1].sum + p[u<<1|1].sum;
p[u].num = p[u<<1].num + p[u<<1|1].num - (p[u<<1].r && p[u<<1|1].l);
p[u].l = p[u<<1].l; p[u].r = p[u<<1|1].r;
}
}

void update(int cL,int cR,int in,int L,int R,int u)
{
if(cL <= L && R <= cR)
{
p[u].cnt += in;
}
else
{
int m = (L+R)>>1;
if(m >= cL) update(cL,CR,in,L,m,u<<1);
if(m < cR) update(cL,CR,in,m+1,R,u<<1|1);
}
pushup(L,R,u);
}

面积并

面积并只维护 cnt 和 len 就可以了

1
2
3
4
5
6
7
8
9

res = 0;
for(int i=0;i<save.size() - 1;++i)
{
int L = lower_bound(point.begin(),point.end(),save[i].y1) - point.begin();
int R = lower_bound(point.begin(),point.end(),save[i].y2) - point.begin() - 1;
if(L <= R) update(L,R,save[i].in,0,pn-1,1);
res += p[1].len*(save[i+1].x - save[i].x);
}

周长并

1
2
3
4
5
6
7
8
9
10
11
res = pre = 0;
for(int i=0;i<save.size();++i)
{
int L = lower_bound(point.begin(),point.end(),save[i].y1) - point.begin();
int R = lower_bound(point.begin(),point.end(),save[i].y2) - point.begin() - 1;
if(L <= R)
update(L,R,save[i].in,0,qn-1,1);
res += 2*p[1].num*(save[i+1].x - save[i].x);
res += abs(p[1].len - pre);
pre = p[1].len;
}

体积表面积并

  • 体积并: 在一个面内维护在另一个面内维护面积并,扫描面。
  • 表面积并: 在一个面内维护在另一个面内维护周长并,扫描面。