Pythonで交差する行数を見つけるプログラム

（m、c）のペアの値を含むリストが与えられたとします。これらの値は線を表します。ここで、y =mx+cです。また、lとrの2つの値が与えられます。 x=lからx=hの範囲で互いに交差する線の数を見つける必要があります。

したがって、入力がinput_list =[[4、6]、[-6、10]、[8、12]]、l =0、h =2の場合、出力は2になります。

与えられた写真を見ると、4x + 6=0と-6x+10の線が与えられた範囲内で交差しています。したがって、交差する2つの線があるため、出力は2になります。

これを解決するには、次の手順に従います-

• seg：=インデックスiのペア[（m * l + c、m * h + c、i）とinput_listの値（m、c）を含むリスト]
• リストセグメントを並べ替える
• ans：=0を含むinput_listのサイズの新しいリスト
• c：=segからの新しいマップ
• セグメント内の（x、y、i）ごとに、
  • c [x]> 1の場合、
    • ans [i]：=1
• max_c：=-（10 ^ 10）
• prv：=-（10 ^ 10）
• セグメント内の（x、y、i）ごとに、
  • 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）について、
  • 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