โปรแกรมนับจำนวนเส้นที่กันเองในช่วงที่กำหนดใน Python

กำหนดลิสต์ของคู่ (m, c) แทนเส้นตรง y = mx + c และช่วง x = l ถึง x = h ต้องการหาจำนวนเส้นที่กันกับเส้นอื่นอย่างน้อยหนึ่งเส้นภายในช่วงนั้น

ตัวอย่าง

อินพุต: input_list = [[4, 6], [-6, 10], [8, 12]], l = 0, h = 2 → เอาต์พุต: 2

เส้น y = 4x + 6 และ y = -6x + 10 กันกันภายในช่วง x ∈ [0, 2]

วิธีแก้ปัญหา

1. คำนวณค่า y ที่ x=l และ x=h สำหรับทุกเส้น → ได้ seg = [(y_l, y_h, index)]
2. เรียง seg ตาม y_l แล้ว y_h
3. ตรวจสอบการทับซ้อนที่ x=l (ค่า y_l ซ้ำ)
4. สแกนซ้ายไปขวา: ถ้า y_h ของเส้นปัจจุบัน ≤ max_y_h ก่อนหน้า → กับกัน
5. สแกนขวาไปซ้าย: ถ้า y_h ของเส้นปัจจุบัน ≥ min_y_h หลังหน้า → กับกัน
6. นับเส้นที่ติดธงว่ากัน

ตัวอย่างโค้ด

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] * len(input_list)
    c = Counter(seg)
    
    # ตรวจสอบจุดตัดที่ x = l
    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))

อินพุต / เอาต์พุต

Input:  [[4, 6], [-6, 10], [8, 12]], 0, 2
Output: 2

หลักการ: เส้นสองเส้นกันในช่วง [l, h] ก็ต่อเมื่อลำดับ y ที่ x=l และ x=h สลับกัน (หนึ่งเส้นอยู่เหนือแล้วตามด้วยอยู่ล่าง) ใช้ sweeping algorithm ตรวจสอบได้ใน O(n log n)