Cho danh sách các cặp (m, c) đại diện cho đường thẳng y = mx + c. Cho khoảng [l, h]. Đếm số đường thẳng có giao điểm với đường thẳng khác trong khoảng x ∈ [l, h].
Ví dụ
Input: lines=[[4,6],[-6,10],[8,12]], l=0, h=2 → Output: 2
Đường 4x+6 và -6x+10 giao nhau trong [0,2]. Đường 8x+12 không giao với hai đường kia trong khoảng này.
Thuật toán (Sweep Line tại hai đầu mút)
Đường thẳng y = mx + c tại x=l có giá trị y_l = ml + c, tại x=h có y_h = mh + c. Hai đường giao nhau trong [l,h] ⟺ thứ tự của chúng tại x=l khác thứ tự tại x=h.
- Tính mảng
seg= [(y_l, y_h, index)] cho mỗi đường - Sắp xếp seg theo y_l
- Duyệt seg theo thứ tự y_l tăng dần:
- Nếu cùng y_l (song song tại l) → cả hai giao nhau
- Theo dõi max y_h đã thấy. Nếu y_h hiện tại ≤ max_y_h → giao nhau
- Duyệt ngược seg (theo y_l giảm dần):
- Theo dõi min y_h. Nếu y_h hiện tại ≥ min_y_h → giao nhau
- Đếm số đường bị đánh dấu giao nhau
Mã nguồn
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)
# Kiểm tra trùng y_l
for (x, y, i) in seg:
if c[x] > 1:
ans[i] = 1
# Duyệt tăng dần y_l
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
# Duyệt giảm dần y_l
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)) # Output: 2Giải thích trực quan
Đường thẳng là hàm tuyến tính. Hai đường giao nhau trong đoạn ⟺ chúng "cắt" nhau, tức là thứ tự y tại l ngược với thứ tự y tại h. Thuật toán phát hiện nghịch thế (inversion) trong dãy y_h khi sắp xếp theo y_l.