পাইথনে কয়টি লাইন ছেদ করে তা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদেরকে একটি তালিকা দেওয়া হয়েছে যাতে (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) এবং ইনপুট_লিস্টে মান (m, c) ধারণকারী একটি তালিকা]
তালিকা বাছাই করুন
উত্তর :=0s ধারণকারী ইনপুট_লিস্টের আকারের একটি নতুন তালিকা
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)
  - prv :=x
min_c =10^10
prv =10 ^ 10
সেগ বিপরীতে প্রতিটি (x, y, i) জন্য, করুন
- যদি x prv এর মত হয়, তাহলে
  - উত্তর[i] :=1
- যদি y>=min_c, তারপর
  - উত্তর[i] :=1
- min_c :=সর্বনিম্ন (min_c, y)
- prv :=x
তালিকার উপাদানের যোগফল (উত্তর)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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