我是新手阿，刚来这个论坛。希望大虾们帮忙!
原题：
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++ ， 其他的语言我都不懂

首先看看两弦什么时候会相交，很显然相交的两弦满足下面这个性质：一条弦的端点在另外一条的两侧。
怎么定义这个两侧呢？我们先把这些端点排序：按照这些点与圆心连线和X轴的夹角大小排序。很显然如果弦AB，CD如果满足点序A>C>B>D这类情况就相交。接下来无非是统计这类情况的数量。

注意到点C在A，B之间，我们定义一个量S。S=AB之间某种的点的数量,这些点满足：它们是某弦的起始点（一个弦有两端点，排序在前的为起始点)，他们对应的弦的终止点不在AB间。很显然S的大小就等于与AB相交，且起始点在AB中的弦的数量，统计所有的S求和就可以得到需要的结果.
接下来就是怎么计算S的问题.可以按照序从小到大对端点进行扫描，并且定义一个序号Key=0（初始值为0）

讨论被扫描点：
（1）它是起始点:记录下该点的Key，Key++;
(2)它是终止点：Key--;S=Key-起始点对应的Key；Sum+=S
看上面的东西，其实Key有点栈的思想，可以联想到括号匹配的进栈与脱括号。

复杂度：排序复杂度可以用快排，O(NlogN),扫描复杂度为O(N)，所以复杂度是O(NlogN)

恩 有一个疑问：
一条弦的 起始点和终止点的 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 前面的线段对应的 末节点 也一起考虑的话，计数时 好像会出现问题。

可以先利用所有的起始节点构造一棵树，并且把所有附加数据记为0，表示没有插入，静态的一般就可以这样。
树状数组和一般的数组没什么两样。只是它是有序的，这样在它上面可以做树的操作，对于d[l..r]，d[(l+r)/2]就是它的根，d[l..(l+r)/2-1]是左子树，d[(l+r)/2+1..r]是右子树

恩 我明白了。谢谢了。

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

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