求助：
原题：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++代码，别的语言我不会......

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

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

明白了 不过，如果 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) 可能会被分到一起而被误认为是重叠吧？

恩 线段树确实是 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 时间。 但是能不能通过 特殊的结构 降低这个值呢？
我们一起想想吧！

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

想想 三维的情况

恩 而且二维线段树也是 log n 时间

矩形重叠的情况 应该可以直接用 二维线段树吧 ？ 那样的话 连扫描排序都不用了 呵呵。


不过有个问题。。。会不会占用太多的空间了。。
因为一开始并不清楚 每个立方体到底会被分到什么位置。。。所以不能很好的确定每个数的边界
一维情况可以先扫描一遍，确定有哪些分隔点。
但是二维情况如果要节省空间的话，
第二维的划分是附属在第一维情况下的，即在第一维的不同位置处第二维的划分方式不同。然而这一步的实现需要的时间能不能保证在 n log n 呢？
如果在第一维的不同位置 第二维的 划分方法都一样的话，那就会要 n*n 的储存空间了

我在想:拓展到 m 维的话有没有什么通法？（线段树 占的空间随 m 指数增大阿）

我想到一种方法： 空间上和m是线性的 但是时间上就不知道了。。。。。（但肯定不会超过 n^2)

是这样的，由于如果重叠的话，两个立方体 应该要在所有的维度上 都重叠，所一如下设计：

首先，还是对 x轴扫描，排序。 ------------ n log n
然后建立 y 轴的 和 z 轴的 两个树。（这个树上面提到过，这里是只能提供判断功能的简化版）
每个节点上只有一个位置所标，和一该节点为根的子树的节点数。
那么每次插入位置时就可以知道该节点在树中的序号（位置重合就放在一个节点上，节点数+1，重合的节点考虑序号时考虑边界条件）。
每次加入线段时，将两个点分别加入（线段中位置靠前的点先加入，以免后加入的点影响前一个点的序号） ---------log n
然后看线段中两个点的序号，如果不连续，那么其中就有别的点，序号之差就是其中的其他的节点的个数。 ------------ 1
分别计算 y 轴 和 x 轴的情况。取其中所夹的节点数 较少的 那个轴，对所夹的节点作遍历，依次比较其所在立方体是否与插入的立方体重合。 --------- ？
程序运行完 还没有重叠的情况的话，就是没有了。

其实还可以 直接建立 x y z 轴的三个树。每次全部插入（就没有删除了），取最少的所夹节点做依次比较。


这个方法所用空间的话 应该是 m*n 的空间，时间是 n log n + n *(log n +1 + ?)

关键是其中的 ？ 应该是多少.....能不能控制在 log n 时间里呢？


加我qq啊！ 我给你发了短消息了。

那个方法好像 ? 所需的时间确实是 n 时间
不过可以有效地降低 n 的系数 呵呵 ， 而且m 越大 其系数越小

我再想想有没有什么好的办法吧。。。。