СРООООЧННООО C. Пересекающиеся отрезки

Question

СРООООЧННООО C. Пересекающиеся отрезки

Владимир Мещеряков Ученик (78), на голосовании 2 дня назад

Даны два массива a и b длины N из целых чисел.
Рассмотрим множество, состоящее из отрезков,
соединяющих точки (0,a i) и (1,bi) для 1≤i≤N.
Найдите количество отрезков этого множества,
которые не пересекаются с другими отрезками.
Обратите внимание, что пересекающимися считаются отрезки,
имеющие хотя бы одну общую точку. То есть отрезки,
имеющие одинаковый конец, пересекаются. Например,
на картинке отрезки, заданные точками [(0,2),(1,5)] и [(0,4),(1,5)] считаются пересекающимися.
В первой строке ввода находится единственное число N — количество отрезков.
В следующих N строках находится по два целых числа, разделенных пробелом — ai и bi, задающие координаты i-го отрезка.
Гарантируется, что все отрезки, заданные во вводе различны,
то есть при i≠j выполнено не менее одного из условий ai ≠ aj и bi ≠ bj.реши на пайтоне
Пример 1
Ввод Вывод
5 1
1 4
2 5
3 1
4 5
5 6
Пример 2
Ввод Вывод
5 1
2 6
3 9
4 2
6 9
9 10
РЕШИТЬ НА ПИТОНЕ

Answer 1

 def count_non_intersecting_segments(N, segments): 
    # Function to check if two segments intersect 
    def intersects(segment1, segment2): 
        a1, b1 = segment1 
        a2, b2 = segment2 
        return not (b1 < b2 and a1 < a2 or b2 < b1 and a2 < a1) 
 
    # Array to keep track of intersection count for each segment 
    intersection_count = [0] * N 
 
    # Check every pair of segments 
    for i in range(N): 
        for j in range(i + 1, N): 
            if intersects(segments[i], segments[j]): 
                intersection_count[i] += 1 
                intersection_count[j] += 1 
 
    # Count segments that do not intersect with any other segment 
    non_intersecting_count = sum( 
        1 for count in intersection_count if count == 0) 
 
    return non_intersecting_count 
 
 
# Read input 
N = int(input().strip()) 
segments = [tuple(map(int, input().strip().split())) for _ in range(N)] 
 
# Calculate and print the result 
print(count_non_intersecting_segments(N, segments))

Answer 2

отрезки i и j пересекаются, если signum(a[i]-a[j]) != signum(b[i]-b[j]) или signum(a[i]-a[j])=0 или signum(b[i]-b[j])=0. В остальном - не вижу проблем.

Answer 3

 N = int(input()) 
segments = [tuple(sorted(map(int, input().split()))) for _ in range(N)] 
 
events = [] 
for i, (y1, y2) in enumerate(segments): 
    events.append((y1, 'start', i)) 
    events.append((y2, 'end', i)) 
 
events.sort(key=lambda x: (x[0], x[1] == 'start')) 
 
active_segments = set() 
intersecting_segments = set() 
 
for y, event_type, index in events: 
    if event_type == 'start': 
        if active_segments: 
            intersecting_segments.add(index) 
            intersecting_segments.update(active_segments) 
        active_segments.add(index) 
    else: 
        active_segments.remove(index) 
 
non_intersecting_count = N - len(intersecting_segments) 
print(non_intersecting_count)

Answer 4

Попробуйте разобраться сложность ~n(n-1)/2:
найдены все пересечения.

 def b_key(s): 
    return s[1] 
#        
a=[1,4,2,7,10,-1] 
b=[2,3,2,5,0,1] 
# 
crss=0 
x0=[(a[i],b[i]) for i in range(len(a))] 
x0.sort() 
while len(x0)>1: 
    x1=x0[1:] 
    x1.sort(key=b_key) 
    for t in x1: 
        if x0[0][1]        crss +=1 
    x0=x0[1:] 
print(crss)