算法导论14.18

【题目】现有一个圆上的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)
  }

原文地址:https://www.cnblogs.com/longdouhzt/p/2111798.html