ACMP 608: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=608 ACMP #608 — Про любовь] == Похожие задачи == * Инт…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 9: | Строка 9: | ||
# Построить множество недопустимых точек (если совпадают противоположные углы двух препятствий); | # Построить множество недопустимых точек (если совпадают противоположные углы двух препятствий); | ||
# Построить множество недопустимых отрезков (если имеют общую часть противоположные стороны двух препятствий); | # Построить множество недопустимых отрезков (если имеют общую часть противоположные стороны двух препятствий); | ||
# Проверить отрезок AB: если он не имеет внутренних пересечений с препятствиями, не содержит недопустимых | # Проверить отрезок AB: если он не имеет '''внутренних''' пересечений с препятствиями, не содержит недопустимых точек и отрезков, то ответ — его середина; | ||
# Построить лучи AC и BC, где C — углы препятствий; | # Построить лучи AC и BC, где C — углы препятствий; | ||
# Для каждой пары ( | # Для каждой пары лучей (ACi, BCj), если они пересекаются, найти точку пересечения P и проверить отрезки AP и BP (аналогично (4)). Если подходят, то ответ — P; | ||
# Если подходящих пар лучей нет, то ответ — NO. | # Если подходящих пар лучей нет, то ответ — NO. | ||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Пересечения]] | [[Category: Задачи: Пересечения]] | ||
Текущая версия от 17:29, 1 июня 2017
Ссылка на задачу
Похожие задачи
Комментарии
- Прочитать входные данные;
- Построить множество недопустимых точек (если совпадают противоположные углы двух препятствий);
- Построить множество недопустимых отрезков (если имеют общую часть противоположные стороны двух препятствий);
- Проверить отрезок AB: если он не имеет внутренних пересечений с препятствиями, не содержит недопустимых точек и отрезков, то ответ — его середина;
- Построить лучи AC и BC, где C — углы препятствий;
- Для каждой пары лучей (ACi, BCj), если они пересекаются, найти точку пересечения P и проверить отрезки AP и BP (аналогично (4)). Если подходят, то ответ — P;
- Если подходящих пар лучей нет, то ответ — NO.