โปรแกรมหาจำนวนเส้นตัดกันใน Python

สมมติว่าเราได้รับรายการที่มีค่าเป็นคู่ของ (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]
• เรียงลำดับรายการ
• ans :=รายการใหม่ของขนาดของ input_list ที่มี 0s
• c :=แผนที่ใหม่จาก seg
• สำหรับแต่ละ (x, y, i) ใน seg ทำ
  • ถ้า c[x]> 1 แล้ว
    • อัน[i] :=1
• max_c :=-(10 ^ 10)
• prv :=-(10 ^ 10)
• สำหรับแต่ละ (x, y, i) ใน seg ทำ
  • ถ้า 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
• ผลตอบแทนรวมขององค์ประกอบของรายการ (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