【题目】现有一个圆上的n条铉，每条铉都是按其端点来定义的。请给出一个能在O(n log n)的算法，确定圆内相交铉的对数（例如：如果n条铉都是直径，他们交于圆心，则正确的答案为C(n,2),组合数）。另外任意两条铉没有公共点。

【解答】[转]

　　通过角度来判断两条弦是否相交，这样可以在O(n*logn)内完成。

　　对于两条弦P1P2和Q1Q2来说（顺时针），圆心与端点形成的向量有一个角度A

　　如果A(P1)<A(Q1)<A(P2)<A(Q2)或者A(Q1)<A(P1)<A(Q2)<A(P2)，这样角度区间“交叉”就意味着两条弦有交叉。

　　通过角度来统计交叉弦的对数，和“逆序对”的问题本质上是一样的

　　这可以看做是“顺序统计树”的典型应用。

　　我们判断两条弦是否相交的依据还是上面提到的“角度”区间是否有“交叉”现象发生

　（注意一个区间包含另一个区间的情况不能算作“交叉”）

　　首先n条弦共2n个端点，每个端点对于圆心来说，都对应一个[0,2*pi)内的角度。

　　我们按角度大小（实际上就是逆时针方向）对这2n个角度进行排序，这一步需要花费O(n*logn)

　　对于每条弦来说，它的两个端点都可以看做是“事件点”：从0角度开始逆时针在圆上扫描，遇到弦的第一个点可以看成是弦的“起点”，遇到的第二个点看成是弦的“终点”。

　　然后，我们用一棵“顺序统计树”来辅助进行处理（初始化当然为空）。

　　按照角度小到大的顺序遍历这2n个端点：

　　如果该端点是某条弦X的“起点”

　　{

　　  将弦X插入顺序统计树中（以X的“起点”角度作为key）；

　　}

　　如果该端点是某条弦X的“终点”

　　{

 　　 统计出目前这棵树中有多少条弦的“起点”角度比X的“起点”角度大，这就是与X相交的弦的数量；

  　　 //对于顺序统计树来说，上面这步只要O(logn)就能实现

 　　 将弦X从顺序统计树中删除； //这一步同样只需要O(logn)

　　}