c++ - 寻找对的更有效方法

Question

我最近遇到了一个问题，该问题要求找到好的圆对的数量。当通过连接第一个圆上的任意点 P1 和第二个圆上的 P2 可以获得给定的距离时，就形成了一对好的圆。我们有 N 个圆和 Q 个距离。接下来的 N 行包含圆心的坐标(X、Y)及其半径 R .之后，下一个Q 列出了要检查的距离。

以下约束适用:

2 ≤ N ≤ 10³

1 ≤ Q ≤ 5⋅10⁵

X,Y ≤ |2⋅10⁵|

1 ≤ R ≤ 2⋅10⁵

0 ≤ K ≤ 10⁶

执行时间必须 < 1 秒。

这里，K 是要检查的距离。

删除了我的代码，因为它是正在进行的竞赛的一部分

我的代码只被部分接受，我花了几个小时试图为这个问题找到一个有效的算法。任何人都可以提供一个有效的方法来解决这个问题，以便解决 TLE 问题吗？

Answer 1

这是我可以从脑海中想到的一个可能的解决方案:

• 遍历每对圆 (c₁, c₂) 并计算两个值 (P.S (c₁, c₂) 不同于 (c₂, c₁))
  1. 如果 c₂ 完全位于 c₁ 内，则忽略这对。
  2. Value₁ - 圆 c₁ 和 c₂ 之间的最短距离，即 < em>它们的中心之间的距离 - r₁ - r₂ 对于不相交的圆，0 对于相交的圆和 r ₂ - dist - r₁ 对于 c₁ 位于 c₂ 内的情况。<
  3. Value₂ - r₁ 应增加的最小值，以便 c₁ 完全吞没 c ₂ 使得它们根本不相交 - 这是它们中心之间的距离 + r₂ - r₁ 用于不相交或相交的圆，dist + r2 用于休息。
• 这个范围 [Value₁, Value₂] 定义了圆 c 的半径的数量₁ 应该增加，使其与 c₂ 相交，在我们的例子中由 K 定义。如果 K 属于范围 [Value₁ , Value₂], 那么我们可以保证在 c₁ 退出>1 和 c₂ 上的点 P₂ 使得它们之间的距离为 K。这是因为如果我们增加 c_{1< 的半径/sub> 在该范围内，它将与 c2 相交。}
• 上述操作的时间复杂度为 O(n²)。我们可以从所有可能的圆对中收集所有范围，并回答任何查询，我们只需要检查是否存在给定 K 所在的范围。
• 为了方便查询，我们可以使用二叉索引树来存储我们的范围，其中我们在索引 Value₁ 处添加 +1，在索引处添加 -1 (Value₂ + 1) 用于二叉索引树，然后对于每个查询，我们检查索引 K 上的读取是否 > 0。这使我们能够返回 O 中任何查询的答案(日志(K))。构建树的成本是 O(N²log(K)) - 包括形成所有圆对。
• 我们还可以使用辅助数组而不是二叉索引树来回答 O(1) 中的查询，如果需要，我愿意讨论其范围。

至于辅助数组方法，初始化一个长度为 K 的数组，即 10^6，所有元素初始设置为 0。现在维护一个所有 Value₁ 的最小堆和另一个所有的最小堆值 Value₂。 现在，

aux_array = [0, 0, ... ]
curVal = 0
for i in range(0, 10^6):
  while minHeapValue1.root() == i:
     curVal += 1
     minHeapValue1.rootPop()
  while minHeapValue2.root() == i:
     curVal -= 1
     minHeapValue2.rootPop()
  aux_array[i] = curVal

现在如果 aux_array[query_k_value] > 0，则表示有一个范围包含 query_k_value，否则不包含。

因此问题的总时间复杂度为 O(Qlog(K) + N²log(K))。