有N个矩形互不相交，假设都放在A数组里，
现有任意的第N+1个矩形B，求B与A数组的并集，此并集用若干个互不相交的矩形表示。补充下，矩形是正交的，也就是说是平行于坐标轴的，没有旋转的。
任何语言实现都可以。
--------------------------------------
另外，对于C++里的CRgn这个类的内部实现，是怎样实现的？我觉得好神奇。

遍历任意两个矩形的四个顶点，也就是八个顶点，找到x、y轴上的最小和最大值（xMin、xMax、yMin、yMax），然后组成并集矩形[(xMin, yMin), (xMin, yMax), (xMax, yMax), (xMax, yMin)]，然后依次重复，直到最后只剩一个矩形。这个是最笨的方法了，应该可以优化。

我来画张图：

有要求长方型个数最少么？

我想到一种解决方案。
1，先将所有长方形抽象成X坐标相等的两条边，并赋予开始边和结束边的属性。
2，将以上边按X顺序排序，如果X相等则按Y逆序排序，得到队列。
3，从左端开始查找X最小的边（A），如果为结束边，则从队列中删除，并继续查找。
4，顺序查找下一条边（B）（X的值不相等）。
5，如果两条边在Y轴上的投影有所重叠，则得到一个长方形，X轴上为A.X~B.X，Y轴上的范围为A.Y1~A.Y2，保留。将B边分割成三段，如图：
得到C1,C2,C3，并抛弃与结束边投影相重合的部分（如果B为结束边，则删除C2,C3）从队列删除A边与B边，并将得到的边加入到原先B边的位置，然后继续重复3，直到队列以空。
以上这种方法对于中间镂空的情况都满足。。。。大概吧。。。

非常感谢，其实我想的也和你的这个有点类似，但我犯了一个很大的错误，我将边分解为点来分析，导致边之间的关联断裂，于是不得不做了很多修正措施。也导致分解出的矩形很多。我的错误就在于，没有很好的跟随人的直观思维，以后吸取教训。对了，你的这个思路还有一个问题没讲清楚，就是开始边和结束边的寻找问题。不过这个简单，我已搞定。总之一句话，谢谢你。