我是新手阿，刚来这个论坛。希望大虾们帮忙!
原题：
Consider n chords on a circle, each defined by its endpoints. Describe an O(n lg n)-time algorithm for determining the number of pairs of chords that intersect inside the circle. (For example, if the n chords are all diameters that meet at the center, then the correct answer is nC2.) Assume that no two chords share an endpoint.

我这样翻译：
圆周上有 N 条弦，无任何两条弦在 圆周上 有交点。
每条弦 在圆周上的两个交点 的位置给出（比如用角坐标）。
求：一共有 多少对 弦 他们在圆内有交点。（n条弦共交点的话，算nC2对）
要求 在 N log N 时间内实现.

给文字描述的思路即可 .
如果一定要编程实现的话 请用c++ ， 其他的语言我都不懂

恩 有一个疑问：
一条弦的 起始点和终止点的 key之差 其增加是因为 有别的弦的起始点在其中， 其减少是因为 有别的弦的终止点 在其中。
但是 其中的终止点 并不一定是 其中的起始点 所对应的 终止点啊。
那这样计数 会不会有问题呢？

我表述的可能不是很清楚。。。。大概就是说 这个模型并不符合 先进先出的 关系啊。

不知道楼上考虑到这个问题没有？ 还是说有的地方我没有理解？

阿 我想到一种办法 你看一下对不对：

首先 把所有的起始节点建立一个搜索树 A，并在每个节点上记录 以此节点为根的子树中的节点数r ------- n log n 时间
然后倒着遍历这个数。

对于每一起始节点I，找到与之对应的末节点 i，然后将末节点"插入"A中。
实际上并不插入，只是找到他在A中的位置，从而知道在i 后面的起始节点数 Si(通过插入的路径上的每个节点的r以及他的左右子女的r -----log n 时间)
然后将i插入另一个搜索树 B（真的插入）。B 树上的 每个节点 也记录了以他为根的子树的节点数。
插入的过程中 也就可以算出 当前 B 树中排在 i 后面的末节点数 Ei. ------ log n 时间。
则 Ei-Si 就是 起始点在 I 和 i 中间，终止点 在 i 后面的线段数。

算出每个 Ei-Si 累加 就是 所得结果了。

遍历树需时间也是 n* log n
所以总需时就是 n log n 了。（为了保证log n, 可以用平衡了的树）

不过这个方法 前面的系数肯定很大 ，但总算是把n log n 满足了 呵呵。
帮忙看看有没有漏洞。

树状数组是什么？ 把树的每个节点储存在数组中吗？ 那构造的时候 怎么满足 插入操作呢？ （构造时 应该是 一个一个的把节点插入吧）

我觉得 末节点组成的树不能一开始就构造好 应为最后计算的一定要是 当前 树中i后面的 末节点数，
如果把 起始点在 I 前面的线段对应的 末节点 也一起考虑的话，计数时 好像会出现问题。

恩 我明白了。谢谢了。

不过我又碰到新的问题了 呵呵。
这回变成二维的了.....不过只用判断有没有，不用计数了。 新的帖子，希望去看一下。

最近在看书。。。很多练习题都不会做。。。。