파이썬에서 얼마나 많은 라인이 교차하는지 찾는 프로그램

(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 :=인덱스 i에 대한 쌍 [(m * l + c, m * h + c, i) 및 input_list의 값(m, c)]을 포함하는 목록
• 목록 세그먼트 정렬
• ans :=0을 포함하는 input_list 크기의 새 목록
• c :=세그먼트의 새 지도
• 세그의 각 (x, y, i)에 대해 다음을 수행합니다.
  • c[x]> 1이면
    • ans[i] :=1
• 최대_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