Даны три выпуклых многоугольника. Необходимо проверить, существуют ли точки, лежащие одновременно внутри всех трех данных выпуклых многоугольников. Как можно решить эту задачу за линию? Для двух выпуклых многоугольников — понятно(сумма Минковского), но как для трех?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 3 | awoo | 161 |
| 4 | maroonrk | 152 |
| 4 | nor | 152 |
| 6 | -is-this-fft- | 151 |
| 7 | TheScrasse | 148 |
| 8 | atcoder_official | 146 |
| 9 | Petr | 145 |
| 10 | pajenegod | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.06.2024 12:12:04 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
Сумма Минковского и метод включения-икслючения.
Можно поконкретнее?)
Можно представить каждый многоугольник как набор полуплоскостей, дающих его в пересечении. Тогда задача сводится к тому, чтобы проверить, что пересечение набора полуплоскостей непусто. Это можно делать в среднем за O(n), если пошаффлить полуплоскости и добавлять их по одной, поддерживая самую верхнюю точку пересечения.
Легко придумать пример, в котором всегда будет O(n^2). Что-то похожее на звезду давида для трех многоугольников.
Чего будет O(n^2)? Каждый многоугольник добавляет линейное количество плоскостей, а алгоритм в среднем за линию от количества полуплоскостей работает.
Линия для добавления плоскостей, а для добавления полуплоскости — еще линия от количества вершин в "общем" множестве. Или я неправильно понял?
мы поддерживаем только самую верхнюю точку, а не находим все точки пересечения.
Не совсем понятно, каким образом поддерживать самую верхнюю вершину. Вы могли бы это пояснить?
сначала самая верхняя точка — какая-нибудь бесконечно высокая. При рассмотрении очередной полуплоскости может быть 2 случая:
1) верхняя точка принадлежит этой полуплоскости
2) не принадлежит
В первом случае верхняя точка не изменится. Во втором случае новая верхняя точка будет лежать на границе рассматриваемой полуплоскости. Для того, чтобы ее найти, пройдемся по всем ранее добавленным плоскостям, пересечение полуплоскости с границей — луч (в общем случае), т. е. нужно найти пересечение лучей и выбрать верхнюю точку этого пересечения.
На самом деле, в задаче автора поста мы имеем только 3 многоугольника = 3 отсортированных множества полуплоскостей. Объединять отсортированные множества мы умеем за O(N * log K), где N — суммарный размер, а K — количество множеств, но т.к. в этой задаче K — константа, имеем асимптотику O(N) даже в худшем случае.
Я правильно понимаю, что под словом "объединять" вы имеете ввиду находить пересечение? И если это так, то где можно почитать о способе за O(N * log K) об этом?
Есть такой человек, зовут его Per Austrin, он публикует разборы финалов ACM ICPC. В начале каждого разбора он приводит дисклеймер, вот его важная часть:
Вам чтение разборов такого формата явно не дается, судя по всему, из-за проблем с последней частью и с самостоятельным мышлением :).
NuM уже объяснил Вам, что многоугольник можно задать множеством полуплоскостей, пересечением которых он является. Т.о. для нахождения пересечения нескольких многоугольников нам нужно объединить множества плоскостей, задающих многоугольники, и выкинуть оттуда лишние полуплоскости. Выкидывание лишних полуплоскостей — это и есть алгоритм пересечения полуплоскостей, который можно реализовать за линию с помощью дека, при условии, что наши полуплоскости отсортированы по углу поворота их нормали. Очевидно, что многоугольник, заданный в фиксированном порядке обхода, можно считать отсортированным множеством полуплоскостей.
Как объединить k отсортированных множеств? Тупой вариант — завести приоритетную очередь, которая будет содержать наименьшие не добавленные в ответ элементы из каждого множества. Более умный вариант (будет работать явно быстрее в случае небольшого k) — на каждом шаге объединять два наименьших множества за линию, пока у нас не останется одно множество (если нужно доказательство — смотрите доказательство алгоритма Хаффмана).
Все теперь понятно. Спасибо)