Суммарная длина это как найти

27 задание – ScanLine (сканирующая прямая)

Введение

Сейчас в базе заданий ЕГЭ задач на отрезки мало, но они вполне могут быть на экзамене. Для начала разберемся, что такое отрезки и с чем их едят?

Задачи на отрезки обычно описаны примерно так:

Вам дано множество отрезков:

• найдите длину которую они суммарно занимают на прямой
• найдите суммарную длину для нескольких видов отрезков на прямой
• Сожмите множество, соединяя или удаляя некоторые отрезки, чтобы они покрывали ту же область на прямой
• найдите максимальное количество отрезков, пересекающихся друг с другом на участке прямой(длины > 0)
• найдите количество участков прямой, где пересекаются ровно X отрезков (где X натурально число)

Ещё 3 вида задач, которые маловероятны на ЕГЭ, но которые умеет решать ScanLine

• найдите количество точек принадлежащих прямоугольнику с координатами x1, y1, x2, y2
• найдите площадь поверхности, которую занимают множество прямоугольников
• найдите максимальное количество пересекающихся отрезков на плоскости

Идея сканирующей прямой

Давайте представим каждый отрезок как пару точек: его начало и конец. После отсортируем наши точки,
чтобы по ним пробежаться “сканирующей прямой” и обработать.

segments = [(1, 10), (2, 5), (3, 15)]
points = []
for start, end in segments:
    points += [(start, 1)]  # 1  - начало отрезка
    points += [(end, -1)]   # -1 - конец отрезка
points.sort()  # [(1, 1), (2, 1), (3, 1), (5, -1), (10, -1), (15, -1)]
# Важное замечание по поводу сортировки, в НЕКОТОРЫХ случаях сортировать надо так,
# чтобы конец (-1) был перед началом (1). Но в каких-то задачах наоборот.
# Встроенная сортировка будет в случае (5, 1) и (5, -1) сортировать как [(5, -1), (5, 1)]

for point in points:
    pass  # сюда обработчик (сканирующая прямая)

Суммарная длина занимаемая всеми отрезками

Сформулируем задачу в формате ЕГЭ

Имеется набор данных, состоящий из отрезков лежащих на прямой (отрезок это пара целых чисел).
Вам требуется найти суммарную длину прямой, которую эти отрезки покрывают.
Гарантируется, что (ОТВЕТ В ЗАДАЧЕ ВЕРНЫЙ) в отрезках координата начала меньше координаты конца.
Программа должна напечатать одно число – длину, соответствующую условиям задачи.

Входные данные.

Даны два входных файла (файл A и файл B),
каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 1e6).
Каждая из следующих N строк содержит два натуральных числа в диапазоне
от -1e9 до 1e9 включительно.

Пояснение к примеру

Итоговая суммарная длинна равна 7-1 + 9-8 = 6 + 1 = 7

Для такой задачи метод сканирующей прямо как раз нам подходит!

with open("27.txt", "r") as file:
    n = int(file.readline())
    segments = [list(map(int, file.readline().split())) for _ in range(n)]

points = []
for start, end in segments:
    points += [(start, 1)]      # 1 - начало отрезка
    points += [(end, -1)]       # -1 - конец отрезка
points.sort()

amount_of_segments = 0          # нынешнее количество пересекающихся отрезков
length = 0                      # суммарная длинна
prev_p = 0                      # координаты последней точки

for p, t in points:             # координата точки и её тип (начало/конец)
    if amount_of_segments > 0:  # если хотя бы один отрезок есть
        length += p - prev_p    # добавляем разницу координат в длину
    prev_p = p
    amount_of_segments += t     # добавляем тип (смотри пояснения)

print(length)

Давайте разбираться что тут происходит!

1. Мы ввели счётчик, который отвечает за количество пересекающихся отрезков на нашем промежутке. Он является ВАЖНОЙ деталью этого алгоритма
2. Если счётчик больше 0, значит что у нас хотя бы один отрезок лежит на промежутке от prev_p до p, значит эту длину можно спокойно вносить в нашу сумму
3. amount_of_segments += t, эта строка означает что если мы встретили начало отрезка, то мы увеличиваем счётчик отрезков на 1, а если встретили конец, то -1 (на 1 отрезок стало меньше). Именно по этому мы так поделили наши отрезки на (1 – начало), (-1 – конец).

Если основная идея ясна, идём дальше!

Суммарная длина нескольких видов отрезков

Имеется упорядоченный набор данных, состоящий из отрезков, лежащих на прямой (отрезок это тройка целых чисел, где 1 и 2 число – координаты начала и конца, 3 число – тип отрезка).
Отрезки упорядочены по времени их появления, то есть отрезки, идущие раньше могут быть перекрыты отрезками, идущими позже (не может одновременно быть 2-х и более различных типов отрезков на одном участке прямой).
Вам требуется найти для каждого типа суммарную длину прямой, которую отрезки этого типа покрывают.

Значение S – это произведение этих найденных сумм.
Гарантируется, что (ОТВЕТ В ЗАДАЧЕ ВЕРНЫЙ) в отрезках координата начала меньше координаты конца.
Программа должна напечатать одно число – значение S.

Входные данные.

Даны два входных файла (файл A и файл B),
каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 1e6).
Каждая из следующих N строк содержит три натуральных числа в диапазоне
от -1e9 до 1e9 включительно.

Пояснение к примеру

Произведение – 8:

• Суммарная длина типа1 (красных) – 4
• Суммарная длина типа2 (зелёных) – 2
• Суммарная длина типа3 (синих) – 1

from collections import defaultdict

with open("27.txt", "r") as file:
    n = int(file.readline())
    segments = [list(map(int, file.readline().split())) for _ in range(n)]
points = []
for start, end, color in segments:
    points += [(start, 1, color)]  # 1 - начало отрезка, ДОБАВЛЯЕМ ЦВЕТ так как он нам важен
    points += [(end, -1, color)]   # 1 - конец отрезка,  ДОБАВЛЯЕМ ЦВЕТ так как он нам важен
points.sort()

colors = []                        # стек где последний элемент - нынешний тип отрезка
color_length = defaultdict(int)    # словарь цвет-суммарная длина этого цвета
prev_p = 0                         # координаты последней точки
for p, t, c in points:             # координата, тип(начало/конец), цвет
    if colors:                     # если есть хотя бы один начавшийся и пока не закончившийся отрезок
        color_length[colors[-1]] += p - prev_p  # добавляем к сумме длин отрезков этого цвета промежуток от предыдущей точки до текущей
    prev_p = p

    if t == 1:                     # если текущая точка - начало отрезка
        colors.append(c)           # кладем его цвет на верх стека
    else:                          # если конец
        colors.pop()               # удаляем цвет с вершины стека(кстати, colors[-1] будет равен с, подумайте почему)

S = 1    # Считаем значение S
for key, val in color_length.items():
    S *= val
print(S)  # Выводим его

Идея очень похожа на решение задачи с одним типом отрезков:

1. Заводим стек (если неясно что это, дайте знать, я опишу базовые структуры данных) типов. Почему именно стек? В контексте этого решения на вершине стека всегда будет лежать последний начавшийся отрезок. Этот отрезок можно легко “закончить”, сняв его с вершины стека.
2. Заводим словарь, в котором будем хранить ответы тип:суммарная_длинна_этого_типа
3. В случае если на стеке уже лежит хотя бы один цвет (if colors), прибавляем к ответу расстояние от начала предыдущего отрезка до текущей точки.
4. Если текущая точка – начало отрезка, кладем его цвет на стек. Иначе – удаляем.

Я открыта для вопросов, так что если они возникли, пишите в группе или в личку

Сжатие множества отрезков

Имеется набор данных, состоящий из отрезков лежащих на прямой (отрезок это пара целых чисел).
Вам требуется переделать множество так, чтобы оно содержало в себе как можно меньше отрезков, но чтобы оно покрывало такие же промежутки прямой, что и оригинальное множество.
Гарантируется, что (ОТВЕТ В ЗАДАЧЕ ВЕРНЫЙ) в отрезках координата начала меньше координаты конца.
Программа должна напечатать одно число – размер минимального множества.

Входные данные.

Даны два входных файла (файл A и файл B),
каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 1e6).
Каждая из следующих N строк содержит два натуральных числа в диапазоне
от -1e9 до 1e9 включительно.

Пояснение к примеру

Мы можем переделать входные данные на множество размера 2 с отрезками: 1-7 и 8-9

Посмотрим как тут ScanLine может нам помочь:

with open("27.txt", "r") as file:
    n = int(file.readline())
    segments = [list(map(int, file.readline().split())) for _ in range(n)]
points = []
for start, end, color in segments:
    points += [(start, 1)]  # 1 - начало отрезка
    points += [(end, -1)]   # 1 - конец отрезка
points.sort(key=lambda a: [a[0], -a[1]])  # ВАЖНО, нам надо чтобы начало шло первее конца


compressed = []
amount_of_segments = 0
previous_start = 0
for p, t in points:
    if amount_of_segments == 0 and t == 1:   # если сейчас 0 отрезков, и появился новый
        previous_start = p                   # записываем новый старт
    if amount_of_segments == 1 and t == -1:      # если сейчас 1 отрезок, и мы встретили конец
        compressed.append([previous_start, p])   # добавляем сжатый отрезок в список
    amount_of_segments += t
print(len(compressed))

Важные моменты в этой идее:

1. Нам нужно изменить сортировку точек. Это надо чтобы при пересечении отрезков в виде 1-4 4-6, у нас не обнулялся счётчик с количеством. Иначе в этом случае мы получим ответ не 1 (1-6), а 2 (1-4 и 4-6)
2. compressed это список полученных сжатых отрезков. В данной задаче нам хранить сами отрезки необязательно, но если поменять условие на найдите колличество отрезков умноженное на длину максимального или что-то ещё сложнее. То наличие этого списка вам поможет легко решить любую модификацию.

Максимальное количество отрезков пересекающихся друг с другом

Имеется набор данных, состоящий из отрезков, лежащих на прямой (отрезок это пара целых чисел).
Вам требуется найти максимальное количество отрезков, которые пересекаются друг с другом (под пересечением имеется ввиду наложение отрезков, то-есть отрезки 1-4 4-5 не пересекаются, когда отрезки 1-4 3-5 пересекаются).
Гарантируется, что (ОТВЕТ В ЗАДАЧЕ ВЕРНЫЙ) в отрезках координата начала меньше координаты конца.
Программа должна напечатать одно число – искомое количество отрезков.

Входные данные.

Даны два входных файла (файл A и файл B),
каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 1e6).
Каждая из следующих N строк содержит два натуральных числа в диапазоне
от -1e9 до 1e9 включительно.

Пояснение к примеру

На промежутке 3-4 у нас пересекается аж 3 отрезка: 1-4, 2-4, 3-5

Задача такая же простая, как и на сумму, только теперь вместо суммы мы будем поддерживать максимум.

Попробуйте решить эту задачу самостоятельно.

Код решающий задачу

with open("27.txt", "r") as file:
    n = int(file.readline())
    segments = [list(map(int, file.readline().split())) for _ in range(n)]

points = []
for start, end in segments:
    points += [(start, 1)]  # 1 - начало отрезка
    points += [(end, -1)]  # -1 - конец отрезка
points.sort()

amount_of_segments = 0  # нынешнее количество пересекающихся отрезков
max_intersection = 0    # максимальное пересечение

for p, t in points:  # координата точки и её тип (начало/конец)
    # максимум среди нынешнего количества пересечения и максимального
    max_intersection = max(max_intersection, amount_of_segments) 
    amount_of_segments += t  # добавляем тип (смотри пояснения)

print(max_intersection)

Главная идея:

1. Заменить счётчик суммы на максимальное пересечение

Количество отрезков, где пересекаются ровно X

Имеется набор данных, состоящий из отрезков лежащих на прямой (отрезок это пара целых чисел).
Вам требуется найти количество отрезков в исходном наборе, которые имеют пересечения с X и более другими отрезками (под пересечением имеет ввиду наложение отрезков, то-есть отрезки 1-4 4-5 не пересекаются, когда отрезки 1-4 3-5 пересекаются).
Гарантируется, что (ОТВЕТ В ЗАДАЧЕ ВЕРНЫЙ) в отрезках координата начала меньше координаты конца.
Программа должна напечатать одно число – искомое количество отрезков.

Входные данные.

Даны два входных файла (файл A и файл B),
каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 1e6) и число X (1 ≤ X ≤ N).
Каждая из следующих N строк содержит два натуральных числа в диапазоне
от -1e9 до 1e9 включительно.

Пояснение к примеру

• Отрезок 1-4 пересекается с отрезками 2-4 и 3-6 (2 ≥ 2), поэтому он входит в наш ответ
• Отрезок 2-4 пересекается с отрезками 1-4 и 3-6 (2 ≥ 2), поэтому он входит в наш ответ
• Отрезок 3-6 пересекается с отрезками 1-4 и 2-4 (2 ≥ 2), поэтому он входит в наш ответ
• Отрезок 5-7 пересекается ТОЛЬКО с 3-6 (1 < 2), поэтому он НЕ входит в наш ответ
• Отрезок 8-9 не пересекается ни с чем (0 < 2), поэтому он НЕ входит в наш ответ

Это достаточно сложная задача. Её основная сложность в том, что если концы двух отрезков одинаковые,
то мы можем потерять какой-то отрезок из ответа (см. пример). Так что этот случай нужно обработать дополнительно или придумать какую-то более интересную идею…

with open("27/ScanLine/input_x_or_more.txt", "r") as file:
    n, x = map(int, file.readline().split())
    segments = [list(map(int, file.readline().split())) for _ in range(n)]

points = []
for i, (start, end) in enumerate(segments):  # давайте пронумеруем отрезки, чтобы их отличать друг от друга
    points += [(start, 1, i)]  # 1 - начало отрезка
    points += [(end, -1, i)]   # -1 - конец отрезка
points.sort()


answer = set()            # ответ (индексы отрезков которые имеют x или более пересечений)
current_segments = set()  # нынешние отрезки (которые сейчас открыты)
prev_p = 0

for p, t, i in points:  # координата точки, её тип (начало/конец) и индекс отрезка
    if len(current_segments) > x:  # если отрезок пересекается с x или более отрезками
        answer |= current_segments  # добавляем в ответ всё наше множество отрезков

    if t == 1:   # добавляем новый отрезок в список нынешних
        current_segments.add(i)
    if t == -1:  # удаляем отрезок из списка нынешних
        current_segments.remove(i)  

print(len(answer))

Главные идеи:

1. Мы храним все индексы нынешних отрезков (и ответа) в set’е, чтобы у нас удалялись повторения

Заключение

ScanLine очень крутая идея, которая решает множество задач на отрезки (но, к сожалению, не все). В случае появления
задач на отрезки важно подумать, может ли сканирующая прямая облегчить решение задачи. И если может, перепроверьте ваш алгоритм на дополнительных тестах.

Очень советую разобрать в дополнении к моей методичке, дополнительные ресурсы ниже.

Ресурсы

Если что-то было непонятно, советую изучить дополнительные ресурсы:

• Очень советую эту статью от Tinkoff Generation для укрепления материала
• Расширенная задача для “2D отрезков” на плоскости
  • Более простое объяснение алгоритма от ИТМО
• БЕСПЛАТНЫЕ слитые курсы ЛКШ с задачами и разборами, прям советую решить для проверки знаний
• Ещё задачи с тестирующей системой (HARD)

Контакты

• Мой телеграм
• Чат с будущими стобальниками

Отдельное спасибо редактору – Екатерине Максимовой <3