पायथन में कितनी रेखाएं प्रतिच्छेद करती हैं यह ढूंढने का प्रोग्राम

मान लीजिए हमें एक लिस्ट दी गई है जिसमें (m, c) मानों के जोड़े हैं। ये मान एक रेखा को दर्शाते हैं, जहां y = mx + c। हमें दो मान l और h भी दिए गए हैं। हमें उन रेखाओं की संख्या ढूंढनी है जो x = l से x = h की रेंज में एक-दूसरे को प्रतिच्छेद करती हैं।

इसलिए, यदि इनपुट input_list = [[4, 6], [-6, 10], [8, 12]], l = 0, h = 2 है, तो आउटपुट 2 होगा।

यदि हम दी गई फोटो को देखें, तो रेखाएं 4x + 6 = 0 और -6x + 10 दी गई रेंज में प्रतिच्छेद करती हैं। तो, दो रेखाएं प्रतिच्छेद कर रही हैं, इसलिए आउटपुट 2 है।

समाधान दृष्टिकोण

दोनों बाउंड्स (l और h) पर प्रत्येक रेखा के 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