求助：
原题：VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume that each rectangle is rectilinearly oriented (sides parallel to the x- and y-axis), so that a representation of a rectangle consists of its minimum and maximum x- and y-coordinates. Give an O(n lg n)-time algorithm to decide whether or not a set of rectangles so represented contains two rectangles that overlap. Your algorithm need not report all intersecting pairs, but it must report that an overlap exists if one rectangle entirely covers another, even if the boundary lines do not intersect. (Hint: Move a "sweep" line across the set of rectangles.)

我的翻译： n 个矩形，其边要么与x轴平行，要么与y轴平行。每个矩形的四个顶点的坐标都给出。
问： 这n个矩形中 有没有两个矩形有相互重叠的部分。（只用给出 有还是没有，不用求出有多少对）
要求 在 n log n 时间内完成。
(Hint: Move a "sweep" line across the set of rectangles.)--〉提示：将一个扫描线扫过整个矩形集（？）



如果只是一维的话，直接用树做就可以了。但问题是 现在是二维的， 连怎么构造树我都没有思路（关键是怎么有效的划分）
还有那个提示。。。。不明白什么意思。

只用给出文字表述的思路即可，或者请用c++代码，别的语言我不会......

这个问题并不困难，像hint说的那样，将一扫描线扫过整个矩形，我们不妨让扫描线和y轴平行，从最左开始扫描.
如果碰到某矩形平行y轴的左边那条边条边，就把这条边插入到某个数据结构中，如果碰到某矩形平行y轴的右边那条边，就把这条边从这个数据结构中删除，如果碰到在插入边时，和前面插入的边有重叠，那么就是矩形重叠了。
扫描复杂度是N，于是要求插入删除复杂度为O（NlogN）。前面提到的数据结构应该用“线段树”，楼主可以去网上找一些关于这个数据结构的了论文.

.....郁闷阿 找了半天 要么就是问什么是线段树，要么就是只在归纳中提到了线段树。。。。
我看得那本书上倒是有一个 Interval Tree 不知道是不是线段树 （翻译问题。。。。）

线段树的结构描述多不多啊。。。不多的话能不能简要描述一下

线段树是一种储存线段（更确切地说是整数区间吧）的数据结构，它是这么定义的,如果我们要存的区间范围为[a,b]，那线段树的根就表示区间[a,b]，它的左儿子表示区间[a,(a+b)/2]，右儿子表示区间[(a+b)/2,b];然后左儿子的左右儿子又是把左儿子的左右区间分成两半。直到所有叶子节点的区间长度为1。没个节点都有一个标记t表示该区间被插入几次.插入一个线段(区间)[x,y]的时候是这么插入的，把[x,y]插入以[a,b]为根的线段树，如果[x,y]在[a,(a+b)/2]之间，插入到左子树，如果[x,y]在[(a+b)/2,b]之间，插入到右子树，如果[x,y]=[a,b]，[a,b]对应的t++，最后一种情况：分别把[x,(a+b)/2],[（a+b)/2,y]插入到左,右子树，删除的操作和插入一样，只不过是t--，经过一些附加处理它还可以统计插入的区间的并集的总长度等等。插入和删除操作的复杂度都是logN

在这里并没有保证区间是整数，但是可以做“离散化”的线段树。

明白了 不过，如果 x < (a+b)/2 < y 的话 就会变成两部分插入。那就不能保证 log n 了吧（或者说 log n 是期望值？）

我还想到一个办法：
其它都是一样的，就是储存的树 用另一种树 替代 线段树。

该树保存的全部是线段的 左点或右点 （y轴的话 就是 上点和下点），但是这些点是分开保存的（分散在数的不同位置）。
节点上记录这样一些信息： 该点的值 v 左点为1 右点为-1 ，以该点为根的子树中的 所有点的值的和 s，
以该点为根的子树中的点的个数 s，该节点上点的个数 c，该节点为根的子树中，最大的重叠数 o。
如果有相同坐标的点，那么就插入到一起 将c +1，同时 左点则将v +1，右点则将 v -1.

每次插入一条边 就将左右两个节点都插入（先左后右），然后记录他们在树中的位置（由于有相同坐标的点，算位置时考虑是取左值还是右值）
如果中间有其它的点，那么就说明有重叠了。
删除时要维护。


做这题的话，节点上不用储存这么多信息。
但是这个树，还可以用来找到现有线段中被最多的线段覆盖的点，这就是我为什么还设计了其它的一些保存在节点上的值。
唉 用这个树的题就是矩形的前一道题......可惜我当时没明白 hint 是什么意思，结果没往这方面想。。。。

啊~~~这样做似乎更快：
还是对那个树的结构的更新。

由于只要出现重合 就可以结束判断了。所以这样实现这个树：
每个节点上都储存一条线段。
开始时是空树。

每次插入或者删除时：
当前树中所有的线段都是 不重合的。（应为如果重合，该过程就已经终止了）
这样插入：如果插入的线段和根有重叠，则找到重合的情况
否则 其要么在根的左边,要么在右边。
如果对应的子女不为空,则第归， --------- log n
如果为空,则将该线段作为其子女。
删除时 只用找到并删除节点就可以了。 -----log n

全部过一遍之后 如果没有发现重合就是没有重合了。

线段树可能不能满足精度要求。。。。(0.001 ,0.002) 和(0.0021 ,0.003) 可能会被分到一起而被误认为是重叠吧？

线段树的复杂度的确是O(logN)但是证明我不会，（0.001 ,0.002)我说过了可以用离散化，比如矩形的点坐标可能有{1,3,4,5}那基本区间就可以是[1,3],[3,4][4,5];如果是{0.1,0.2,0.3}那基本区间是[0.1,0.2],[0.2,0.3];

恩 线段树确实是 log N ，
我这样证的：
（x,y) 被分成两端后 (x,r) (r,y) 那么r 会与下面要划分的边界重合。
那么之后 (x,r) 如果再被划分，(x,t) (t,r) 那么 (t,r) 将恰好是 一个被分入的那个子树的根，不会继续向下搜索。只有 （x,t)向下发展。
而 t 也将是和边界重合，所以保持了 (x,r) 被分割后只有一个部分会继续向下搜索的性质。

所以 (x,y） 不会被无限制的分成n 块向下搜索。同时只会至多有 两块 被向下搜索。


精度问题我是这样想的：
比如说是 (2,3) (10,13) (15.002,15.003) (15.005,15.006)
那么精度分细了 就会增大树的长度，分粗了 就无法区分那两个相隔十分紧密的 节点了。



我觉得这个题可以 拓展以下， 变成立方体三维的，那么判断的时间可以最少是多少呢？
如果两两比较的话 需要 n^2 时间。 但是能不能通过 特殊的结构 降低这个值呢？
我们一起想想吧！

楼上没理解我的意思,精度不一定是固定的，完全可以离散化处理.
比如可能的端点集合为{1, 4 ,5 ,70，100}
那线段树的根就是[1,100]左子树可以是[1,5]右子树是[5,100]，
对应的线段树:
[1,100]
/ \
[1,5] [5,100]
/ \ / \
[1,4] [4,5] [5,70] [70,100]
这样已经可以满足所有可能的插入了

哦 原来是这样......

想想 三维的情况