不瞭解題中“碰撞”的含義，我理解為矩形覆蓋部分有重疊就算碰撞了。

我們先看簡單的一維情況：一條直線上散落著若干給定端點座標線段，怎麼判斷各線段是否有交叉？

一種N*logN的演算法是，標記好每個端點是哪一條線段的左端點或右端點後，對所有端點按座標排序。如果線段a的左端點處於線段b的左右端點之間，而a的右端點處於線段b的左右端點之外，則線段a和b是有交叉的。所以排序+遍歷就可以解決了。

補充說明：如果線段a和左端點和右端點均線上段b的左右端點之間，則線段a處於線段b內部，也就是包含關係。計算“包含關係”和計算“交叉關係”的複雜度是一樣的。

於是，在二位平面上，可以先把所有矩形投影到x軸上，按一維方式判斷它們在x軸上是否交叉，如果在x軸上有交叉，則判斷對應矩形在y軸上投影線段是否交叉。x軸和y軸均有交叉，則可以判定兩個矩形碰撞。

正方形的完全覆蓋關係也可以同樣計算。

複雜度是排序N*logN，遍歷N，綜合起來N*logN。

布吉島有沒有效能更優的演算法。