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 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告