Это очередной пост из серии "записки дилетанта о спортивном программировании". Тут как в том анекдоте: "Лев Толстой очень любил играть на балалайке, но не умел. Порой пишет очередную главу, а сам думает: тренди-бренди, тренди-бренди...". В общем, точно про меня и спортивное программирование.
Итак, задача с крайне простой постановкой.
Дан произвольный двудольный граф: "n" вершин слева, "m" справа и некоторое количество дуг. Требуется ответить на вопрос: сколько раз дуги графа пересекаются.
В данном примере n=5, m=4, десять дуг: 1-1, 1-2, 2-1, 2-2, 3-3, 4-1, 4-3, 5-1, 5-2, 5-4, количество пересечений: 10.
Факт пересения рассматривается всегда попарно. Например, если уж так случилось, и три дуги пересекаются в одной геометрической точке, формально пересечений все равно три, а не одно.
Задача имеет решение за O(n*m).
Сообщения
Комментариев нет:
Отправить комментарий