时间戳

首页 > 解决方案 > 查找三角形内的纠缠数

algorithm - 查找三角形内的纠缠数

问题描述

示例图像

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

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

我很困惑，真的不知道如何开始设计这个，任何帮助将不胜感激！

标签： algorithm

解决方案

让我们称三角形ABC。设 MN 和 PQ 为 2 个弹丸。有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. 迭代从 A 到 B 的弹丸，对于每个弹丸 i (MN)，(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 上距离 A 小于 AM 的弹丸的 pj 之和。

然后我们对每对边都进行此操作（因此第一种类型为 3 次，第二种类型为 6 次）。所以总共应该是 O(N logN)。

推荐阅读