पायथन में कितनी रेखाएँ प्रतिच्छेद करती हैं, यह जानने के लिए कार्यक्रम

मान लीजिए हमें एक सूची दी गई है जिसमें (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 में]
सूची क्रमित करें
उत्तर :=0s युक्त input_list के आकार की एक नई सूची
c :=seg से एक नया नक्शा
सेग में प्रत्येक (x, y, i) के लिए, करें
- अगर c[x]> 1, तो
  - उत्तर[i] :=1
max_c :=-(10 ^ 10)
prv :=-(10 ^ 10)
सेग में प्रत्येक (x, y, i) के लिए, करें
- यदि x, prv के समान है, तो
  - उत्तर[i] :=1
- यदि y <=max_c, तो
  - उत्तर[i] :=1
- max_c :=अधिकतम (max_c, y)
  - पीआरवी:=एक्स
min_c =10 ^ 10
पीआरवी =10 ^ 10
प्रत्येक के लिए (x, y, i) seg उलट में, करें
- यदि x, prv के समान है, तो
  - उत्तर[i] :=1
- यदि y>=min_c, तो
  - उत्तर[i] :=1
- min_c :=न्यूनतम (min_c, y)
- पीआरवी:=एक्स
सूची के तत्वों का रिटर्न योग (उत्तर)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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