Олимпиадный тренинг

Задача . Mirrors


Задача

Темы: поиск в глубину и подобное

Фермер Джон установил N отражающих заборов (зеркал) (1 <= N <= 200) в различных местах фермы и надеется что сможет видеть из своего дома в точке (0,0) до амбара в точке (a,b).
На 2D-карте фермы Джона забор i показывается коротким отрезком с центром в точке с целочисленными координатами (xi, yi) и повернутым на 45 градусов (либо так '/', либо так '/'). Например, забор типа '/' в позиции (3,5) может быть описан как отрезок из (2.9,4.9) в (3.1,5.1). Все центры заборов, а также амбар лежат в точках с целочисленными координатами в диапазоне от -1,000,000...1,000,000. Центр ни одного забора не лежит в точках (0,0) или (a,b).
ФД планирует сидеть в своем доме в позиции (0,0) и смотреть вправо (вдоль по оси X в положительном направлении). Он хочет видеть точку (a,b). Однако одно зеркало установлено неправильно (например, '\' вместо '/'). Пожалуйста, выведите индекс первого зеркала в списке ФД, повернув которое (с '/' на '\' или наоборот) ФД сможет увидеть точку (a,b).
Если ФД уже может видеть точку (a,b) не поворачивая ни одно зеркало, выведите 0. Если невозможно увидеть (a,b) после переключения ровно одного зеркала, выведите -1.
PROBLEM NAME: mirrors
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа, N, a, b.
* Строки 2..1+N: Строка i+1 описывает зеркало i и содержит либо xi yi / либо xi yi \ Символ / или \ указывает ориентацию зеркала.
Формат выходных данных
* Строка 1: Индекс первого зеркала, переключение которого позволит ФД видеть точку (a,b). Если ФД уже может видеть точку (a,b) выведите 0, если переключение только одного зеркала не позволит видеть точку (a,b), выведите -1.
Примечание
Переключение зеркала в позиции (3,2) позволит ФД увидеть точку (a,b).
3 .\..... 2 //./--B 1 ...|... 0 H--/... 0123456
Примеры
№Входные данныеВыходные данные
1 
5 6 2
3 0 /
0 2 /
1 2 /
3 2 \
1 3 \
 
4
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет