注：更正一下：在英文原版書中。“請給出一個能在O(nlgn)”時間里確定一組矩形中是否有兩個重疊的算法。

”而不是中文版的 O(lgn).由于這個問題里涉及的排序算法就至少是O(nlgn)。

基本思想：

??????? 經(jīng)提示用以矩形橫坐標(biāo)x為軸作為掃描線。從全部矩形x最小值到矩陣x最大值，當(dāng)然在這之前要對全部矩形的橫坐標(biāo)x做一個排序，我用的是歸并排序。

??????? 掃描過程如圖所看到的的三個矩形中，從x1開始掃描。遇到矩形Gi的左x坐標(biāo)，將Gi的縱坐標(biāo)y的低端點(diǎn)和高端點(diǎn)組成的區(qū)間插入?yún)^(qū)間樹后，推斷矩陣Gi與區(qū)間樹中已有的區(qū)間是否重疊，若重疊則返回真以證明重疊矩形存在，若沒有重疊，則繼續(xù)掃描x。

假設(shè)遇到矩形Gi的右x坐標(biāo),說明再往后掃描就不會與Gi矩形重疊，所以把Gi刪除。如此循環(huán)往復(fù)。

圖中所給三個矩形G1,G2,G3.應(yīng)該從x1掃描到x2程序就自己主動終止證明重疊矩形存在，不會掃描到G3。

??????? 整體來看：①先做歸并排序(時間O(nlgn))? ②再做區(qū)間樹的插入刪除以及重疊操作(O(nlgn)).

代碼例如以下：

"MERGE_SORT.h"頭文件

struct Array {int key;int index; }; void MERGE(struct Array B[],int p,int q,int r) {int n1=q-p+1,n2=r-q,flag=-1,i,j;//不能為數(shù)組A里面的數(shù)。

struct Array *L=new struct Array[n1]; struct Array *R=new struct Array[n2]; for (i=1;i<=n1;i++) { L[i-1].key=B[p+i-1].key; L[i-1].index=B[p+i-1].index; } for (j=1;j<=n2;j++) { R[j-1].key=B[q+j].key; R[j-1].index=B[q+j].index; } L[n1].key=flag; R[n2].key=flag; i=0;j=0; for (int k=p;k<=r;k++) { if (L[i].key==flag) { B[k].key=R[j].key; B[k].index=R[j].index; j++; } else if (R[j].key==flag) { B[k].key=L[i].key; B[k].index=L[i].index; i++; } else if (L[i].key<=R[j].key) { B[k].key=L[i].key; B[k].index=L[i].index; i++; } else { B[k].key=R[j].key; B[k].index=R[j].index; j++; } } } void MERGE_SORT(struct Array B[],int p,int r) { if (p<r) { int q=(p+r)/2; MERGE_SORT(B,p,q); MERGE_SORT(B,q+1,r); MERGE(B,p,q,r); } }

主函數(shù)+區(qū)間樹

#include <iostream> #include <conio.h> #include "MERGE_SORT.h" using namespace std; #define BLACK 0 #define RED 1 #define Nil -1 #define LEN sizeof(struct Tree) #define n 4//矩形的個數(shù) struct Tree*root=NULL; struct Tree*nil=NULL; struct interval {int low,high; }; struct Rectangular {int flag;struct interval x,y; }; struct Tree {struct Tree*right,*left;struct Tree*parent;struct interval Int;int Max;int key;int color; }; int MAX(int a,int b,int c) {int temp=a>b?a:b;return temp>c?temp:c; } void LEFT_ROTATE(struct Tree*x) {//左旋轉(zhuǎn)：分三個步驟①②③來敘述旋轉(zhuǎn)代碼的。struct Tree*y=x->right;//設(shè)置y結(jié)點(diǎn)。

?x->right=y->left;//本行代碼以及以下的if結(jié)構(gòu)表達(dá)的是“y的左孩子成為x的右孩子”。① ?if(y->left!=nil) ?{ ?????? y->left->parent=x; ?} ?y->parent=x->parent;//本行代碼以及以下的if-else結(jié)構(gòu)表達(dá)的過程是“y成為該子樹新的根”。② ?if(x->parent==nil) ?{ ?????? root=y; ?} ?else if(x==x->parent->left) ?{ ?????? x->parent->left=y; ?} ?else x->parent->right=y; ?y->left=x;//本行代碼以及以下一行都表達(dá)了“x成為y的左孩子”。

③ ?x->parent=y; ?y->Max=x->Max; ?x->Max=MAX(x->Int.high,x->left->Max,x->right->Max); } void RIGHT_ROTATE(struct Tree*x) {//右旋轉(zhuǎn)：分三個步驟①②③來敘述旋轉(zhuǎn)代碼的。

?struct Tree*y=x->left;//設(shè)置y結(jié)點(diǎn)。

?x->left=y->right;//本行代碼以及以下的if結(jié)構(gòu)表達(dá)的是“y的左孩子成為x的右孩子”。① ?if(y->right!=nil) ?{ ??y->right->parent=x; ?} ?y->parent=x->parent;//本行代碼以及以下的if-else結(jié)構(gòu)表達(dá)的過程是“y成為該子樹新的根”。② ?if(x->parent==nil) ?{ ??root=y; ?} ?else if(x==x->parent->right) ?{ ??x->parent->right=y; ?} ?else x->parent->left=y; ?y->right=x;//本行代碼以及以下一行都表達(dá)了“x成為y的左孩子”。③ ?x->parent=y; ?y->Max=x->Max; ?x->Max=MAX(x->Int.high,x->left->Max,x->right->Max); } void RB_INSERT_FIXUP(struct Tree*z) { ?? while (z->parent->color==RED) ?? { ??? if (z->parent==z->parent->parent->left) ??? { ???? struct Tree*y=z->parent->parent->right;//叔結(jié)點(diǎn) ???? if (y->color==RED)//情況一：叔結(jié)點(diǎn)為紅色 ???? {//給p1,y,p2著色以保持性質(zhì)5。

而且攻克了z的父結(jié)點(diǎn)和z都是紅色結(jié)點(diǎn)問題 ????? z->parent->color=BLACK; ????? y->color=BLACK; ????? z->parent->parent->color=RED; ????? z=z->parent->parent;//把z的祖父結(jié)點(diǎn)當(dāng)成新結(jié)點(diǎn)z進(jìn)入下一次循環(huán) ???? } ???? else ???? { ????? if (z==z->parent->right)//情況二：檢查z是否是一個右孩子且叔結(jié)點(diǎn)為黑色，前提是p1結(jié)點(diǎn)不是葉子結(jié)點(diǎn) ????? {//使用一個左旋讓情況2轉(zhuǎn)變?yōu)榍闆r3 ?????? z=z->parent; ?????? LEFT_ROTATE(z);//因?yàn)檫M(jìn)入if語句后可知旋轉(zhuǎn)結(jié)點(diǎn)不可能是葉子結(jié)點(diǎn)。這樣就不用推斷z是否是葉子結(jié)點(diǎn)了。

????? } ?????????????? z->parent->color=BLACK;//情況三：是z是一個左孩子且叔結(jié)點(diǎn)為黑色，改變z的父和祖父結(jié)點(diǎn)顏色并做一次右旋，以保持性質(zhì)5 ????? z->parent->parent->color=RED; ????? RIGHT_ROTATE(z->parent->parent);//因?yàn)閜2可能是葉子結(jié)點(diǎn)。所以不妨用一個if推斷 ???? } ??? } ??? else//以下else分支相似于上面,注意到else分支的情況2和情況3所做旋轉(zhuǎn)正好是if分支情況的逆。 ??? { ???? struct Tree*y=z->parent->parent->left; ???? if (y->color==RED) ???? { ????? z->parent->color=BLACK; ????? y->color=BLACK; ????? z->parent->parent->color=RED; ????? z=z->parent->parent; ???? } ???? else ???? { ????? if (z==z->parent->left) ????? { ?????? z=z->parent; ?????? RIGHT_ROTATE(z); ????? } ?????????????? z->parent->color=BLACK; ????? z->parent->parent->color=RED; ????? LEFT_ROTATE(z->parent->parent); ???? } ??? } ?? } ?? root->color=BLACK;//最后給根結(jié)點(diǎn)著為黑色。 } void RB_INSERT(struct Tree* z) { ?z->key=z->Int.low; ?struct Tree*y=nil; ?struct Tree*x=root; ?while (x!=nil) ?{ ??y=x; ??x->Max=MAX(x->Int.high,x->Max,z->Int.high); ??if (z->key<x->key) ??{ ???x=x->left; ??} ??else x=x->right; ?} ?z->parent=y; ?if (y==nil) ?{ ??root=z; ?} ?else if(z->key<y->key) ?{ ??y->left=z; ?} ?else y->right=z; ?z->left=nil;//給插入結(jié)點(diǎn)左右孩子賦值為空。 ?z->right=nil; ?z->color=RED;//給插入結(jié)點(diǎn)著為紅色。 ?z->Max=z->Int.high;//+ ?RB_INSERT_FIXUP(z); } void RB_TRANSPLANT(struct Tree*u,struct Tree*v) { ?if (u->parent==nil) ??root=v; ?else if(u==u->parent->left) ??u->parent->left=v; ?else u->parent->right=v; ?v->parent=u->parent; } //非遞歸版本號的查找二叉查找樹的最小值 struct Tree*ITERATIVE_TREE_MINIMUM(struct Tree*x) { ?while (x->left!=nil) ?{ ??x=x->left; ?} ?return x; } //非遞歸版本號的二叉查找樹查找函數(shù) struct Tree*ITERATIVE_TREE_SEARCH(struct Tree*x,int k) { ?while (x!=nil&&k!=x->key) ?{ ??if (k<x->key) ??{ ???x=x->left; ??} ??else x=x->right; ?} ?return x; } void RB_DELETE_FIXUP(struct Tree*x) { ? struct Tree*w=NULL;//w是x的兄弟結(jié)點(diǎn) ???? while (x!=root&&x->color==BLACK)//假設(shè)x是黑色而且不是根結(jié)點(diǎn)。才進(jìn)行循環(huán)。 ???? {//x是一個具有雙重顏色的結(jié)點(diǎn)，調(diào)整的目的是把x的黑色屬性向上移動。

?? if (x==x->parent->left) ?? { ??? w=x->parent->right; ??? if (w->color==RED)//情況一：x的兄弟結(jié)點(diǎn)w是紅色的。 ??? {//改變w和x.p的顏色+一次旋轉(zhuǎn)使其變?yōu)榍闆r二。三，四。

???? w->color=BLACK; ???? x->parent->color=RED; ???? LEFT_ROTATE(x->parent); ???? w=x->parent->right; ??? } ??? if (w->left->color==BLACK&&w->right->color==BLACK)//情況二：x的兄弟結(jié)點(diǎn)w是黑色的。而且w的兩個子節(jié)點(diǎn)都是黑色。 ??? { ???? w->color=RED;//從x和w上去掉一重黑色。

x還是黑色，而w變?yōu)榧t色。 ???? x=x->parent;//x結(jié)點(diǎn)向上移動成為新的待調(diào)整結(jié)點(diǎn)。 ??? } ??? else ??? { ???? if (w->right->color==BLACK)//情況三：x的兄弟結(jié)點(diǎn)w是黑色的，w的左孩子是紅色的。w的右孩子是黑色的。 ???? {//交換w和w.left的顏色+旋轉(zhuǎn)使其轉(zhuǎn)變?yōu)榍闆r四。

????? w->left->color=BLACK; ????? w->color=RED; ????? RIGHT_ROTATE(w); ????? w=x->parent->right; ???? } ???? w->color=x->parent->color;//以下是情況四：x的兄弟結(jié)點(diǎn)w是黑色的，且w的右孩子是紅色的。

???? x->parent->color=BLACK;//置x.p和w.right為黑色+旋轉(zhuǎn)使其去掉x的額外黑色。

???? w->right->color=BLACK; ???? LEFT_ROTATE(x->parent); ???? x=root;//x成為根結(jié)點(diǎn)，結(jié)束循環(huán)。 ??? } ?? } ?? else//以下和上面的if分支相似。不做累述。 ?? { ???????????? w=x->parent->left; ??? if (w->color==RED) ??? { ???? w->color=BLACK; ???? x->parent->color=RED; ???? RIGHT_ROTATE(x->parent); ???? w=x->parent->left; ??? } ??? if (w->left->color==BLACK&&w->right->color==BLACK) ??? { ???? w->color=RED; ???? x=x->parent; ??? } ??? else ??? { ???? if (w->left->color==BLACK) ???? { ????? w->right->color=BLACK; ????? w->color=RED; ????? LEFT_ROTATE(w); ????? w=x->parent->left; ???? } ???? w->color=x->parent->color; ???? x->parent->color=BLACK; ???? w->left->color=BLACK; ???? RIGHT_ROTATE(x->parent); ???? x=root; ??? } ?? } ???? } ? x->color=BLACK; } void RB_DELETE(struct Tree*z) { ??? struct Tree*y=z,*x;//y為待刪除或待移動結(jié)點(diǎn) ?int y_original_color=y->color;//保存y的原始顏色，為做最后的調(diào)整做準(zhǔn)備。

?if (z->left==nil) ?{ ??x=z->right;//x指向y的唯一子結(jié)點(diǎn)或者是葉子結(jié)點(diǎn)。保存x的蹤跡使其移動到y(tǒng)的原始位置上 ??RB_TRANSPLANT(z,z->right);//把以z.right為根的子樹替換以z為根的子樹。 ?} ?else if (z->right==nil) ?{ ??x=z->left;//x指向y的唯一子結(jié)點(diǎn)或者是葉子結(jié)點(diǎn)，保存x的蹤跡使其移動到y(tǒng)的原始位置上 ??RB_TRANSPLANT(z,z->left);//把以z.left為根的子樹替換以z為根的子樹。 ?} ?else ?{ ??y=ITERATIVE_TREE_MINIMUM(z->right);//找到z.right的后繼。 ??????? y_original_color=y->color;//y的新的原始結(jié)點(diǎn)被重置。 ??x=y->right;//x指向y的唯一子結(jié)點(diǎn)或者是葉子結(jié)點(diǎn)，保存x的蹤跡使其移動到y(tǒng)的原始位置上 ??if (y->parent==z) ??{ ???x->parent=y;//因?yàn)閦的父結(jié)點(diǎn)是要刪除的結(jié)點(diǎn)。所以不能指向它，于是指向y ??} ??else ??{ ???RB_TRANSPLANT(y,y->right);//把以y.right為根的子樹替換以y為根的子樹。 ???y->right=z->right; ???y->right->parent=y; ??} ??RB_TRANSPLANT(z,y);//把以y為根的子樹替換以z為根的子樹。

??y->left=z->left; ??y->left->parent=y; ??y->color=z->color;//把已經(jīng)刪除的結(jié)點(diǎn)顏色賦值給y，保證了y以上的樹結(jié)構(gòu)紅黑性質(zhì)不變。 ?} ?struct Tree*k=x->parent; ?while (k!=nil) ?{ ??k->Max=MAX(k->left->Max,k->right->Max,k->Int.high); ??k=k->parent; ??} ?if(y_original_color==BLACK) //y的原始顏色為黑色。說明須要調(diào)整紅黑顏色。 ??RB_DELETE_FIXUP(x); } bool overlap(struct interval x,struct interval i) { ?if (x.high<i.low||i.high<x.low) ?{ ??return? true;//沒有重疊 ?} ?else ?{ ??return false; ?} } struct Tree *INTERVAL_SEARCH(struct Tree *T,struct interval i) { ?? struct Tree *x=T; ?? while (x!=nil&&overlap(x->Int,i)) ?? { ??? if (x->left!=nil&&x->left->Max>=i.low) ??? { ???? x=x->left; ??? } ??? else x=x->right; ?? } ?? return x; } bool Rectangle_overlap(struct Rectangular A[],struct Array B[]) {//推斷n個矩陣是否重疊，執(zhí)行時間為O(nlgn) ?int i=1; ?while (i!=2*n) ?{ ??if (A[B[i].index].flag==0)//0代表矩形Ri的縱坐標(biāo)的還未進(jìn)入掃描線。 ??{ ???struct Tree*z=new struct Tree[LEN]; ???z->key=A[B[i].index].y.low; ???z->Int.low=A[B[i].index].y.low; ???z->Int.high=A[B[i].index].y.high; ???A[B[i].index].flag=1; ???if (root!=z&&INTERVAL_SEARCH(root,z->Int)!=nil) ???{//假設(shè)矩形重疊存在，那么直接返回。 ????return true; ???} ???RB_INSERT(z);//將這個矩形插入進(jìn)區(qū)間樹 ??} ??else//否則，矩形Ri的縱坐標(biāo)進(jìn)入過掃描線了，那么遇到的橫坐標(biāo)(B[i].key代表橫坐標(biāo))必定是Ri的高端點(diǎn)。 ??{ ???if (i==2*n-1||A[B[i+1].index].y.low!=A[B[i].index].y.high) ???{ ????struct Tree*z=ITERATIVE_TREE_SEARCH(root,A[B[i].index].y.low);//先找到區(qū)間樹中的這個結(jié)點(diǎn)。 ?????? RB_DELETE(z);//從區(qū)間樹中刪除這個矩形。

???} ??} ??i++; ?} ?return false; } void init(struct Rectangular A[],struct Array B[]) {//區(qū)間樹初始化。

?nil=new struct Tree[LEN];//設(shè)置葉子結(jié)點(diǎn) ?nil->key=Nil;nil->color=BLACK; ?root=nil; ?int i=0; ?struct Tree*z=new struct Tree[LEN];//設(shè)置根結(jié)點(diǎn)。 ?z->key=A[B[i].index].y.low; ?z->Int.low=A[B[i].index].y.low; ??? z->Int.high=A[B[i].index].y.high; ?RB_INSERT(z); ?root=z; ?A[B[i].index].flag=1; } int char_int() { ?char ch; ?int i=0,s=0,t=1; ?char ch1[n]={0}; ?while (ch!=' ') ?{ ??if (ch=='#') ??{ ???while (i) ???{ ????cout<<"\b"; ????ch1[i]=' '; ????i--; ???} ??} ??ch=getch(); ??cout<<ch; ??ch1[i++]=ch; ?} ?cout << "\b";//\b退格符號 ?while (i>1) ?{ ??s+=(ch1[i---2]-'0')*t; ??t*=10; ??cout << "\b"; ?} ?return s; } void main() { ?struct Rectangular A[n]={0}; ?struct Array B[2*n]={0}; ?for (int i=0,j=0;i<n,j<2*n;i++,j+=2) ?{ ??cout<<"請輸入第"<<i<<"個矩陣的數(shù)據(jù)：(按#號鍵又一次輸入，按空格鍵結(jié)束輸入)"<<endl; ??cout<<"x的左端點(diǎn)=";cout<<(A[i].x.low=char_int()); ??cout<<" x的右端點(diǎn)=";cout<<(A[i].x.high=char_int()); ??cout<<" y的低端點(diǎn)=";cout<<(A[i].y.low=char_int()); ??cout<<" y的高端點(diǎn)=";cout<<(A[i].y.high=char_int())<<endl; ??B[j].key=A[i].x.low; ??B[j+1].key=A[i].x.high; ??B[j].index=i; ??B[j+1].index=i; ?} ?MERGE_SORT(B,0,2*n-1);//歸并排序。時間為O(nlgn) ?init(A,B); ?if(Rectangle_overlap(A,B)) ?{ ??cout<<"重疊矩陣存在！"<<endl; ?} ?else cout<<"重疊矩陣不存在"<<endl; }

最后測試時注意。和通常輸入數(shù)據(jù)不太一樣的是按空格結(jié)束輸入而且按#號又一次輸入！

例子輸入：



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

總結(jié)

以上是生活随笔為你收集整理的确定一组矩形是否有两个重叠的算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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