ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Тренировочный турнир сезона «Зима — 2019» > задача:


F. Макс и поиск закусочных

Тренировочный турнир сезона «Зима — 2019»

Старт: 01.янв.2019 в 00:00:00
Финиш: 31.янв.2019 в 23:00:00
Осталось: 262:54:01
• Турнирная таблица

Задачи турнира

• A. Площадь и периметр
• B. Макс и приготовление супа
• C. Макс и простая задача
• D. Макс и сооружение города
• E. Никита и интервью
• F. Макс и поиск закусочных
• G. Макс и нестандартная спираль
• H. Макс и новогодние открытки
• I. Макс и распознавание фигур
• J. Макс и муниципальная задача
• K. СириусЛяндия и страсть к оливкам
• P1. Подбор отрезков ленты для од...
• P10. Бегущие огни в диагоналях
• P2. Подбор отрезков ленты для дв...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и поиск закусочных
Макс и поиск закусочных
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Скоро в городе откроет свои кафе знаменитая сеть закусочных. Чтобы жителям города было проще найти ближайшее заведение, менеджеры сети решили выпустить мобильное приложение. Разработку этого приложения доверили самому известному и талантливому программисту — Максу, конечно же.

Всего в городе открываются $$$N$$$ закусочных, пронумерованных от 1 до $$$N$$$. $$$i$$$-я закусочная расположена в точке $$$(X_i; Y_i)$$$ и имеет рейтинг $$$R_i$$$.

Приложение должно по информации о том, где находится человек, определять закусочные, расположенные неподалёку от него — то есть такие, расстояние до которых (по прямой) не превышает $$$D$$$. Из этих закусочных нужно выбрать ту, которая имеет наивысший рейтинг, а если таких несколько — ближайшую. Если наилучших закусочных всё ещё несколько, следует выбрать ту, номер которой меньше.

Помогите приложению Макса найти наилучшую закусочную для каждого клиента.

Входные данные

Первая строка содержит целое число $$$N$$$ ($$$1 \le N \le 100$$$) — количество закусочных.

Следующие $$$N$$$ строк описывают закусочные. Каждая из них содержит целые числа $$$X_i$$$, $$$Y_i$$$ и $$$R_i$$$ ($$$0 \le X_i, Y_i, R_i \le 100$$$) — соответственно координаты закусочной и её рейтинг.

Следующая строка содержит целые числа $$$M$$$ и $$$D$$$ ($$$1 \le M \le 100$$$, $$$1 \le D \le 150$$$) — соответственно количество запросов и максимально допустимое расстояние до закусочной.

Следующие $$$M$$$ строк описывают запросы. Каждая из них содержит целые числа $$$X_j$$$ и $$$Y_j$$$ ($$$0 \le X_j, Y_j \le 100$$$) — координаты клиента, отправившего запрос.

Выходные данные

Выведите $$$M$$$ строк, каждая из которых содержит одно целое число — номер наилучшей закусочной, расположенной неподалёку от клиента, отправившего соответствующий запрос.

Если неподалёку от клиента нет закусочных, выведите в соответствующей строке -1.

Примеры

Входные данные
3
1 1 1
2 2 2
3 3 3
3 2
1 2
0 0
5 3
Выходные данные
2
1
3
Входные данные
4
1 5 3
5 1 5
1 5 2
2 5 5
4 4
1 6
6 1
6 4
8 8
Выходные данные
4
2
2
-1

Для отправки решений необходимо выполнить вход.

www.contester.ru