Python程序：查找有多少条线段相交

假设我们得到一个列表，其中包含成对的值 (m, c)。这些值表示一条直线，其中 y = mx + c。我们还给出两个值 l 和 r。我们需要找出在 x = l 到 x = h 的范围内，有多少条线段彼此相交。

因此，如果输入类似于 input_list = [[4, 6],[-6, 10],[8, 12]]，l = 0，h = 2，则输出将为 2。

如果我们查看给定的图片，直线 4x + 6 = 0 和 -6x + 10 在给定范围内相交。因此，有两条线段相交，所以输出为 2。

为了解决这个问题，我们将遵循以下步骤：

  • seg := 一个包含对的列表 [(m * l + c, m * h + c, i)，其中索引 i 和值 (m, c) 来自 input_list]
  • 对列表 seg 进行排序
  • ans := 一个大小与 input_list 相同的新列表，包含 0
  • c := 一个来自 seg 的新映射
  • 对于每个 (x, y, i) 在 seg 中，执行以下操作：
    • 如果 c[x] > 1，则
      • ans[i] := 1
  • max_c := -(10 ^ 10)
  • prv := -(10 ^ 10)
  • 对于每个 (x, y, i) 在 seg 中，执行以下操作：
    • 如果 x 与 prv 相同，则
      • ans[i] := 1
    • 如果 y <= max_c，则
      • ans[i] := 1
    • max_c := (max_c, y) 中的最大值
      • prv := x
  • min_c = 10 ^ 10
  • prv = 10 ^ 10
  • 对于每个 (x, y, i) 在 seg 中（逆序），执行以下操作：
    • 如果 x 与 prv 相同，则
      • ans[i] := 1
    • 如果 y >= min_c，则
      • ans[i] := 1
    • min_c := (min_c, y) 中的最小值
    • prv := x
  • 返回列表 (ans) 中元素的总和

示例

让我们看看下面的实现来更好地理解：

from collections import Counter

def solve(input_list, l, h):
   seg = [(m * l + c, m * h + c, i) for i, (m, c) in
enumerate(input_list)]
   seg.sort()
   ans = [0 for _ in input_list]
   c = Counter(seg)
   for (x, y, i) in seg:
      if c[x] > 1:
         ans[i] = 1
   max_c = -(10 ** 10)
   prv = -(10 ** 10)
   for (x, y, i) in seg:
      if x == prv:
         ans[i] = 1
      if y <= max_c:
         ans[i] = 1
      max_c = max(max_c, y)
      prv = x
   min_c = 10 ** 10
   prv = 10 ** 10
   for (x, y, i) in seg[::-1]:
      if x == prv:
         ans[i] = 1
      if y >= min_c:
         ans[i] = 1
      min_c = min(min_c, y)
      prv = x
   return sum(ans)

print(solve([[4, 6],[-6, 10],[8, 12]], 0, 2))

输入

[[4, 6],[-6, 10],[8, 12]], 0, 2

输出

2

更新于: 2021年10月19日

433 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告