查找三角形内的纠缠数

大师朋友

范例图片

假设给定的三角形和n个投射物像示例中的线一样。现在，每个弹丸都有一个起点位置，终点位置和一个概率。所有的开始和结束位置都以a表示，tuple (s, alpha) where s is in {0, 1, 2}它指定三角形的边（按顺时针顺序），并0 <= alpha <= 1指定点沿边的距离（也按顺时针顺序）。如果实际上有两个射弹相遇，则它们产生纠缠的概率为pi x pj（其中pi和pj是两个射弹的概率）。

您需要做的是计算该三角形中有n个射弹的可能纠缠的总数，它应该在 O(nlogn)

我很困，不知道该如何开始设计，任何帮助将不胜感激！

9垫

让我们将三角形称为ABC。令MN和PQ为2个射弹。有两种情况：

M，N，P，Q位于ABC的两侧。WOLG，说M和P在AB上，N和Q在AC上，AM> AP。这两个弹丸要穿过AN <AQ。换句话说，这种类型的与MN交叉的射弹是第一点位于AM之外而第二点位于AN之外（又称为NC）的射弹。因此，计算这种纠缠的可能性：
1. 收集以AB和AC结尾的射弹
2. 按与AB上A的距离对弹丸进行排序。
3. 建立并跟踪到AC上与A的距离的范围树（或可以在O（logN）中查询sum（pj使得xj> x）的某种类型的树/数据结构）
4. 对于每个射弹i（MN），将射弹从A迭代到B，（4i）查询范围树中的sum（pj），以使AC到AN上与A的距离相等，（4ii）添加pi * sum（pj）答案（之所以起作用，是因为到目前为止，范围树中的弹丸与AB上的A的距离应小于M），（4iii）将（AN，pi）添加到范围树
第二种类型是当M，N，P，Q位于所有3个边上时。WOLG，说M和P在AB上，N在AC上，Q在BC上。这比较容易，因为必要和充分的条件是AP <AM。因此，我们只需要按与AB上的A的距离对所有从AB开始并在BC上结束的弹丸进行排序，对于每个MN，我们可以查询AB上的AM小于AM的那些弹丸的pj之和。