Условие

Задача является прямым продолжением задачи «Радио-поиск».

Теперь на том же поле сыграем в охоту на «тень».

Внутри поля, представленного декартовой плоскостью в виде квадрата с углами в точках (0; 0) и (1000; 1000), находится «радио-тень» в виде круга диаметром 300 м. Вы можете установить излучатель и приёмник в двух точках поля, выполнить передачу сигнала и получить обратную связь: пришёл сигнал или не пришёл. Если между микрофоном и динамиком есть тень, сигнал не придёт. Если микрофон или динамик в тени – сигнал также не придёт.

Ваша задача – определить координаты центра тени с точностью до 3 м.

Формат входных данных

Ваше решение отправляет одно из двух сообщений.

Выполнение передачи: восклицательный знак, пробел и четыре вещественных числа через пробел – координаты излучателя и приёмника.

Проверка координаты: «собачка», пробел и два вещественных числа через пробел – предполагаемые координаты центра.

После этой команды решение должно завершить работу

Формат выходных данных

Выполнение передачи: одна строка с одним из двух слов, пришёл ли сигнал – `YES` или `NO`.

Проверка координаты: одна строка со словом `OK`.

Для решения этой задачи у вашей команды есть 20 попыток.

Видео-разбор

 

Разборы

Сигнал блокируется круглой тенью. Задача - найти центр тени с точностью до трёх метров, при помощи посылания лучей и получения ответа.

Координаты центра ищем по каждой оси отдельно при помощи бинарного поиска.

Для поиска вертикальной координаты используем горизонтальный луч. Сначала делим поле на четыре равных сегмента при помощи трёх лучей. Таким образом находим сегмент, в котором тень пересекает верхнюю границу сегмента, но не пересекает нижнюю.

Следующим этапом при помощи бинарного поиска уточняем положение нижней границы тени.

Аналогичную операцию проводим для нахождения левой границы тени.

Получив обе координаты, отправляем ответ и завершаем программу.

Last modified: Friday, 15 May 2026, 6:54 AM