পাইথনে কতগুলো রেখা আঁটকাচ্ছে তা বের করার প্রোগ্রাম

একটি লিস্ট দেওয়া আছে যাতে (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 রেখাগুলো দেওয়া রেঞ্জের মধ্যে আঁটকে। সুতরাং দুটি রেখা আঁটকে, আউটপুট ২।

সমাধানের ধাপসমূহ

seg := [(m×l + c, m×h + c, i) for index i, and values (m, c) in input_list] লিস্ট
seg সর্ট করুন
ans := input_list-এর আকারের ০ দিয়ে ইনিশিয়ালাইজড লিস্ট
c := seg থেকে একটি নতুন ম্যাপ
seg-এর প্রতিটি (x, y, i) için:
- যদি c[x] > 1 হয়, তবে ans[i] := 1
max_c := -(10^10), prv := -(10^10)
seg-এর প্রতিটি (x, y, i) için:
- যদি x == prv হয়, তবে ans[i] := 1
- যদি y <= max_c হয়, তবে ans[i] := 1
- max_c := max(max_c, y), prv := x
min_c = 10^10, prv = 10^10
seg-এর রিভার্স অর্ডারে প্রতিটি (x, y, i) için:
- যদি x == prv হয়, তবে ans[i] := 1
- যদি y >= min_c হয়, তবে ans[i] := 1
- min_c := min(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