問題：給出若干個矩形，（給的是矩形左上角和右下角坐標(biāo)），求最后所得圖形的面積/周長；

三個矩形如左圖所示，而若要計算面積，看右圖，用3個矩形各自的面積之和減去重復(fù)部分（紅色和藍(lán)色）的面積

人算很簡單，但是用算法怎么實現(xiàn)呢？

此類問題一般都是用線段樹輔助掃描法來計算；

什么是掃描法？有什么用？怎么用？

可以想象成一根假想的線，將圖從左往右或從右往左或自下而上或自上而下“掃描”一遍，至于掃描的是什么則根據(jù)具體應(yīng)用選擇。

掃描線可以計算矩形面積、周長，可以計算線段交點(diǎn)，可以實現(xiàn)多邊形掃描轉(zhuǎn)換，在圖的處理方面經(jīng)常用到。

這里總結(jié)一下掃描線計算矩形面積和周長的算法。

怎么用？首先，對于之前的圖，除了用總面積減去重合面積，還可以換一種計算方法，如圖：

此圖用4條橫線將整個圖劃分成了5個部分，顯然此時再算面積就可以用各個顏色的部分求和。

想想，這樣計算的整個慢過程：

假設(shè)我們的視線自下而上，首先，我們看到了最下面灰色矩形的下邊，

用這個下邊的長度乘以這條邊和上一條邊的高度差即得到灰色矩形面積，

繼續(xù)看到藍(lán)色的矩形的下邊，雖然藍(lán)色矩形有兩個，但我們計算時自然會用結(jié)合律將兩個矩形的下邊加起來再去乘以同樣的高，

然后重復(fù)這樣的操作，我們最終可以求得整個圖形的面積。

但是，這依舊是人做的，計算機(jī)要怎么實現(xiàn)呢？

首先的問題是，計算機(jī)要怎么保存這張圖這些矩形？

從剛才的過程，我們不難發(fā)現(xiàn)，我們只需要保存這張圖里面的所有水平的邊即可。

對于每條邊，它所擁有的屬性是：這條邊的左右端點(diǎn)（的橫坐標(biāo)），這條邊的高度（縱坐標(biāo)），這條邊屬于矩形的上邊還是下邊（想想為什么保存這個屬性）

剛剛計算中我們遇到兩個藍(lán)色矩形的一部分一眼就能看出這兩個藍(lán)色矩形的‘寬’是多少，用計算機(jī)怎么做到？

線段樹華麗登場!

我們以整個圖最左邊的豎線作為區(qū)間左端點(diǎn)，最右邊的豎線作為區(qū)間右端點(diǎn)，去維護(hù)這個區(qū)間的有效長度（即被覆蓋的長度）

比如掃到第2條邊的時候，有效長度就是兩個藍(lán)色矩形的寬之和。

這樣，我們用掃描線去掃描每一條邊的時候，都需要更新線段樹的有效長度

是如何更新的呢？

如果掃到的這條邊是某矩形的下邊，則往區(qū)間插入這條線段

如果掃到的這條邊是某矩形的上邊，則往區(qū)間刪除這條線段

為什么？自己試著模擬一下就不難發(fā)現(xiàn)：

因為我們是自下而上的掃這個圖，掃到下邊相當(dāng)于剛剛進(jìn)入一個矩形，掃到上邊則是要離開一個矩形

利用線段樹把每條邊的有效長度找到了，也就是找到了每部分的所有矩形的總寬，那么高呢？

高就簡單多了，對于所有的邊，按照高度從小到大排列，那么矩形高就是每相鄰邊之間的高度差

給個例子：HDU 1542 Atlantis

然后看看用代碼具體是怎么實現(xiàn)的：

ps: ? 特別說一下，關(guān)于上邊和下邊的標(biāo)記，用-1標(biāo)記下邊，1標(biāo)記上邊是最合理的（想想為什么，提示：下邊--刪除，上邊--插入）

? ? ? ? 這題橫坐標(biāo)略大，需要離散化處理

#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
using namespace std;
typedef long long ll;
const int N = 111;
struct Edge
{double l,r;//這條線的左右端點(diǎn)的橫坐標(biāo)double h;//這條線的縱坐標(biāo)int f;//這條線是矩形的上邊還是下邊
}e[N<<1];
bool cmp(Edge a,Edge b)
{return a.h < b.h;
}
struct Node
{int l,r;//橫坐標(biāo)的區(qū)間，是橫坐標(biāo)數(shù)組的下標(biāo)int s;//該節(jié)點(diǎn)被覆蓋的情況（是否完全覆蓋）double len;//該區(qū)間被覆蓋的總長度
}q[N*8];
double x[2*N];//橫坐標(biāo)
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l + q[i].r)>>1)
void build(int i,int l,int r)
{q[i].l = l,q[i].r = r;q[i].s = 0;q[i].len = 0;if (l == r) return;int mid = m(i);build(ls,l,mid);build(rs,mid+1,r);
}
void pushup(int i)
{if (q[i].s) //非零，已經(jīng)被整段覆蓋{q[i].len = x[q[i].r+1] - x[q[i].l];}else if (q[i].l == q[i].r) //這是一個點(diǎn)而不是線段{q[i].len = 0;}else //是一條沒有整個區(qū)間被覆蓋的線段，合并左右子的信息{q[i].len = q[ls].len + q[rs].len;}
}
void update(int i,int l,int r,int xx)//這里深刻體會為什么令下邊為1，上邊-1
{                                   //下邊插入邊，上邊刪除邊if (q[i].l == l&&q[i].r == r){q[i].s += xx;pushup(i);//更新區(qū)間被覆蓋de總長度return;}int mid = m(i);if (r <= mid) update(ls,l,r,xx);else if (l > mid) update(rs,l,r,xx);else{update(ls,l,mid,xx);update(rs,mid+1,r,xx);}pushup(i);
}
int main()
{int n;int kas = 0;while (scanf("%d",&n) == 1&&n){int tot = 0;for (int i = 0;i < n;++i){double x1,x2,y1,y2;scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);//輸入一個矩形Edge &t1 = e[tot];Edge &t2 = e[1+tot];t1.l = t2.l = x1,t1.r = t2.r = x2;t1.h = y1;t1.f = 1;t2.h = y2;t2.f = -1;x[tot] = x1;x[tot+1] = x2;tot += 2;}sort(e,e+tot,cmp);//邊按高度從小到大排序（自下而上掃描）sort(x,x+tot);//離散化橫坐標(biāo)int k = 1;for (int i = 1;i < tot;++i){if (x[i] != x[i-1]) //去重{x[k++] = x[i];}}build(1,0,k-1);//離散化后的區(qū)間是[0，k-1]double ans = 0.0;for (int i = 0;i < tot;++i){//因為線段樹維護(hù)的是橫坐標(biāo)們的下標(biāo)，所以對每條邊求出其兩個橫坐標(biāo)對應(yīng)的下標(biāo)int l = lower_bound(x,x+k,e[i].l) - x;//在橫坐標(biāo)數(shù)組里找到這條邊的位置int r = lower_bound(x,x+k,e[i].r) - x - 1;update(1,l,r,e[i].f);//每掃到一條邊就更新橫向的覆蓋lenans += (e[i+1].h - e[i].h)*q[1].len;//q[1]是整個區(qū)間,q[1].k=len是整個區(qū)間的有效長度//計算面積就是用區(qū)間橫向的有效長度乘以兩條邊的高度差（面積是兩條邊里面的部分）}printf("Test case #%d\n",++kas);printf("Total explored area: %.2f\n\n",ans);}return 0;
}

說完了矩形面積，矩形周長的方法自然是類似的，但是周長的計算卻更復(fù)雜些，看這張圖:

周長可以分成兩部分計算，橫線和豎線，如圖將所有彩色的橫線加起來就是橫向的所有長度了

然后可以采用豎直方向的掃描線將豎線的所有長度求出來

那么怎么計算橫線的長度呢？

橫線的長度 = 【現(xiàn)在這次總區(qū)間被覆蓋的程度和上一次總區(qū)間被覆蓋的長度之差的絕對值】

想想為什么要加絕對值（提示：下邊--刪除，上邊--插入）

這樣用自下而上和從左往右的兩次掃描即可得到答案。

但是，這樣的方法顯得有些笨，有沒有更高端的方法呢？

再看一張圖：

看出什么了嗎？這張圖在上面那張圖的基礎(chǔ)上多了幾條豎線。

我的意思是說，我們可以只做一次自下而上的掃描就把橫線豎線都算出來！

豎線的算法和上面說的方法一樣：【現(xiàn)在這次總區(qū)間被覆蓋的程度和上一次總區(qū)間被覆蓋的長度之差的絕對值】

豎線要怎么計算？

首先我們現(xiàn)在改一下線段樹保存的屬性，我們用如下信息記錄線段樹的節(jié)點(diǎn)：

1. l , r : 該節(jié)點(diǎn)代表的線段的左右端點(diǎn)坐標(biāo)

2.len : 這個區(qū)間被覆蓋的長度（即計算時的有效長度）

3.s : 表示這個區(qū)間被覆蓋了幾次

4. lc , rc : 標(biāo)記這個節(jié)點(diǎn)的左右兩個端點(diǎn)是否被覆蓋（0表示沒有，1表示有）

5.num :這個區(qū)間有多少條線段（這個區(qū)間被多少條線段覆蓋）

這里的num涉及到豎線的計算，故解釋一下,舉幾個例子：

? ?若區(qū)間[0,10]被[1,2][4,5]覆蓋，則num = 2

? ?若區(qū)間[0,10]被[1,3][4,5]覆蓋，則num = 1（兩區(qū)間剛好連在一起）

? ?若區(qū)間[0,10]被[1,5][2,6]覆蓋，則num = 1（兩區(qū)間連起來還是一段）

然后就可以計算豎線了：

豎線的長度 = 【下一條即將被掃到的橫線的高度 - 現(xiàn)在掃到的橫線的高度】*2*num

乘2是因為每條線段有兩個端點(diǎn)；

看上圖中棕色線段的豎線有4條，因為棕色的橫線由2條線段組成

白色線段的豎線只有2條，因為白色的橫線由1條線段組成（雖然這1條線段是由許多線段組合而成，但它依舊只算1條線段）

這樣，依舊只掃一次就可以算出周長。

給個例子：HDU 1828Picture

代碼實現(xiàn)：

#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
using namespace std;
typedef long long ll;
const int N = 5007;
const int X = 20007;
const int inf = 1<<29;
struct Edge//掃描線
{int l,r;//左右端點(diǎn)的橫坐標(biāo)int h;//這條線的高度，即縱坐標(biāo)int f;//標(biāo)記這條邊是上邊(-1)還是下邊(1)
}e[N*2];
bool cmp(Edge a,Edge b)
{return a.h < b.h;//高度從小到大排，掃描線自下而上掃
}
struct Node
{int l,r;//該節(jié)點(diǎn)代表的線段的左右端點(diǎn)坐標(biāo)int len;//這個區(qū)間被覆蓋的長度int s;//表示這個區(qū)間被重復(fù)覆蓋了幾次bool lc,rc;//表示這個節(jié)點(diǎn)左右兩個端點(diǎn)是否被覆蓋（0表示沒有被覆蓋，1表示有被覆蓋）int num;//這個區(qū)間有多少條線段（這個區(qū)間被多少條線段覆蓋）//len用來計算橫線 num用來計算豎線
}q[4*X];
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l + q[i].r)>>1)
void pushup(int i)//區(qū)間合并
{if (q[i].s)//整個區(qū)間被覆蓋{q[i].len = q[i].r - q[i].l + 1;q[i].lc = q[i].rc = 1;q[i].num = 1;}else if (q[i].l == q[i].r)//這是一個點(diǎn)而不是一條線段{q[i].len = 0;q[i].lc = q[i].rc = 0;q[i].num = 0;}else //是一條沒有整個區(qū)間被覆蓋的線段，合并左右子的信息{q[i].len = q[ls].len + q[rs].len ;//長度之和q[i].lc = q[ls].lc;q[i].rc = q[rs].rc;//和左兒子共左端點(diǎn)，和右兒子共右端點(diǎn)q[i].num = q[ls].num + q[rs].num  - (q[ls].rc&q[rs].lc);//如果左子的右端點(diǎn)和右子的左端點(diǎn)都被覆蓋了}
}
void build (int i,int l,int r)
{q[i].l = l,q[i].r = r;q[i].s = q[i].len = 0;q[i].lc = q[i].rc = q[i].num = 0;if (l == r) return;int mid = m(i);build(ls,l,mid);build(rs,mid+1,r);
}
void update(int i,int l,int r,int xx)
{if (l == q[i].l && q[i].r == r){q[i].s += xx;pushup(i);return;}int mid = m(i);if (r <= mid) update(ls,l,r,xx);else if (l > mid) update(rs,l,r,xx);else{update(ls,l,mid,xx);update(rs,mid+1,r,xx);}pushup(i);
}
int main()
{int n;while (cin>>n){int x1,x2,y1,y2,mx = -inf,mn = inf;int tot = 0;for (int i = 0;i < n;++i){scanf("%d %d %d %d",&x1,&y1,&x2,&y2);mx = max(mx,max(x1,x2));mn = min(mn,min(x1,x2));Edge & t1 = e[tot];Edge & t2 = e[tot+1];t1.l = t2.l = x1,t1.r = t2.r = x2;t1.h = y1;t1.f = 1;t2.h = y2;t2.f = -1;tot += 2;}sort(e,e+tot,cmp);//數(shù)據(jù)小可以不離散化int ans = 0;//計算周長int last = 0;//保存上一次的總區(qū)間的被覆蓋的長度build(1,mn,mx-1);//每兩條橫線之間才會有豎線for (int i = 0;i < tot;++i){update(1,e[i].l,e[i].r-1,e[i].f);//根據(jù)掃描線更新//計算周長//橫線：現(xiàn)在這次總區(qū)間被覆蓋的程度和上一次總區(qū)間被覆蓋的長度之差的絕對值ans += abs(q[1].len - last);//豎線：[下一條橫線的高度-現(xiàn)在這條橫線的高度]*2*numans += (e[i+1].h - e[i].h)*2*q[1].num;last = q[1].len;//每次都要更新上一次總區(qū)間覆蓋的長度}printf("%d\n",ans);}return 0;
}

?

進(jìn)階：

?HDU 1255 覆蓋的面積（線段樹+掃描線求面積【升級版】）

轉(zhuǎn)載于:https://www.cnblogs.com/bytebull/p/5973485.html

總結(jié)

以上是生活随笔為你收集整理的多个矩形，求覆盖面积，周长，及交点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。