Pythonで指定範囲内で交差する直線の本数を求めるプログラム

問題の概要

(m, c) というペアを格納したリストが与えられていると仮定しましょう。これらの値は直線 y = mx + c を表しています。さらに、2つの値 l と r も同時に与えられます。ここで求めたいのは、x = l から x = r までの範囲内で互いに交差する直線の本数です。

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

上の図を見ると、直線 4x + 6 と -6x + 10 が指定された範囲内で交差していることが分かります。つまり、交差している直線は2本あるため、出力は 2 となります。

解決のための手順

この問題を解くには、以下の手順に従います。

• seg の作成: input_list の各インデックス i と値 (m, c) に対して、(m * l + c, m * h + c, i) というタプルを含むリスト seg を作成します。これは、各区間の両端 x = l と x = h における直線の y 座標を表しています。
• リスト seg をソートします。
• ans の初期化: input_list と同じサイズで、すべて 0 を格納した新しいリスト ans を作成します。
• c の作成: seg からマップ(Counter)を新しく作成します。
• seg 内の各 (x, y, i) について次を実行します。
  • c[x] > 1 の場合は、ans[i] := 1 とします。
• max_c := -(10 ^ 10)、prv := -(10 ^ 10) として初期化します。
• seg 内の各 (x, y, i) について順方向に走査します。
  • x が prv と等しい場合は、ans[i] := 1 とします。
  • y が max_c 以下の場合は、ans[i] := 1 とします。
  • max_c := max(max_c, y)、prv := x と更新します。
• min_c := 10 ^ 10、prv := 10 ^ 10 として初期化します。
• seg を逆順に走査しながら、各 (x, y, i) について次を実行します。
  • x が prv と等しい場合は、ans[i] := 1 とします。
  • y が min_c 以上の場合は、ans[i] := 1 とします。
  • min_c := min(min_c, y)、prv := x と更新します。
• 最後に、リスト ans の要素の総和を返します。

このアルゴリズムのポイントは、「区間 [l, h] 上の2つの線分が交差するのは、一方の左端点が他方より高く、右端点が他方より低い(または端点を共有する)場合と一致する」という性質を利用している点です。左端点でソートした後、それまでに見た右端点の最大値・最小値と比較することで、交差の有無を効率的に判定できます。

実装例

理解を深めるために、以下の実装を見てみましょう。

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

全体の計算量はソートが支配的となるため O(n log n) であり、多数の直線が与えられた場合でも効率的に交差判定を行うことができます。