images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 19:48:17

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1503. Сигнальная система

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Барт и Милхаус решили создать сигнальную систему для общения друг с другом. Для генерации сигнала они решили использовать китайскую лазерную указку и расставить на улице зеркала так, чтобы луч прошел от домика на дереве до комнаты Милхауса в обход препятствий: домов, деревьев, почтовых ящиков и т.п. Они выбрали несколько подходящих точек для установки зеркал и хотят использовать расстановку с минимальным количеством зеркал, так как каждое отражение приводит к потере мощности сигнала, а если таких расстановок несколько, то из них выбрать расстановку с минимальной длиной пути луча. Луч лазера не должен проходить через препятствия или касаться их. Луч не должен проходить дважды через одно зеркало и не может проходить через зеркало без отражения. Угол между падающим на зеркало лучом и отраженным должен быть строго меньше 180 градусов.
Напишите программу, которая рассчитывает оптимальную расстановку зеркал для сигнальной системы.
Первая строка ввода содержит шесть целых чисел - количество препятствий `K` (`1 ≤\ K\ ≤\ 100`) и количество точек для установки зеркал `N` (`1\ ≤\ N\ ≤\ 100`), координаты источника лазерного луча `X_S`, `Y_S` и координаты приемника `X_D`, `Y_D` . Далее следует `K` строк, каждая строка содержит четыре целых числа – координаты противоположных углов препятствия (препятствия являются невырожденными прямоугольниками со сторонами параллельными осям координат). Далее следует `N` строк, каждая строка содержит два целых числа – координаты возможной точки для установки зеркала. Все координаты – целые числа в диапазоне от 0 до 1000. Точки для установки зеркал различны, находятся вне препятствий и не соприкасаются с ними. Препятствия не пересекаются, но могут касаться друг друга.
В первой строке вывести одно целое число `M` (`0\ ≤\ M\ ≤\ N`) – количество установленных зеркал. Во второй строке вывести `M` целых чисел – номера точек в порядке прохождения их лучом лазера. Если существует несколько оптимальных расстановок зеркал, то можно вывести любую из них. Если решения не существует, то в первой строке вывести сообщение "No solution" (без кавычек).

Пример ввода

1 3 100 200 700 600
200 300 600 500
0 400
400 200
300 600

Пример вывода

2
1 3
loading