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

Турниры > Тренировочный турнир сезона «Осень — 2018» > задача:


J. Макс и Medieval

Тренировочный турнир сезона «Осень — 2018»

Старт: 06.окт.2018 в 14:00:00
Финиш: 02.ноя.2018 в 23:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (2)

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

• B. Даниил и модульные весы
• C. Макс и RLE
• D. Макс и торрент
• E. Макс и мины
• F. Максимальное произведение
• G. Даниил и ряд врагов
• H. Даниил и составление расписания
• I. Даниил и пропавшие результаты
• J. Макс и Medieval
• P1. Таймер: Код доступа
• P10. Таймер: Упаковка конфет в к...
• P2. Таймер: Планирование процес...
• P3. Таймер: Трассировка циклогра...
• P4. Таймер: Мониторинг кратковре...
• P5. Таймер: Мониторинг длительн...
• P6. Таймер: Планирование размера...
• P7. Таймер: Подача брусков начинки

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

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

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

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

Макс играет в старую, но всё ещё популярную стратегию Medieval.

Против мощи военного гения Макса не смогли выстоять даже такие великие державы, как Франция, Англия, Испания, а также многие другие. Но настал роковой час, и во владения Макса вторглась огромная монгольская орда, стремящаяся разорить его города.

У Макса есть N городов, i-й из которых имеет координаты (XiYi), а также M армий, j-я из которых имеет начальные координаты (XjYj). Монгольская орда имеет начальные координаты (XY).

Армии Макса и монгольская орда могут перемещаться по карте. За один ход армия или орда может переместиться на единицу в любом направлении вдоль оси Ox или Oy либо остаться на месте. Сначала Макс делает ход каждой из своих армий, затем свой ход делает орда.

Макс сумел определить, что монгольская орда перемещается от начальных координат к ближайшему городу (если таких несколько, то к городу с наибольшей координатой Xi; если таких всё ещё несколько, то к городу с наибольшей координатой Yi), разоряет его, затем перемещается к следующему ближайшему (от текущих координат) городу, и так далее.

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

Помогите Максу определить город, в котором нужно собрать все войска.

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

Первая строка содержит целые числа X и Y ( - 109 ≤ X, Y ≤ 109) — координаты вторжения монголов.

Вторая строка содержит целое число N (1 ≤ N ≤ 2000) — количество городов.

Следующие N строк описывают города. Каждая из них содержит целые числа Xi и Yi ( - 109 ≤ Xi, Yi ≤ 109) — координаты города. Координаты всех городов различны.

Следующая строка содержит целое число M (1 ≤ M ≤ 2000) — количество армий.

Следующие M строк описывают армии. Каждая из них содержит целые числа Xj и Yj ( - 109 ≤ Xj, Yj ≤ 109) — координаты армии. Координаты всех армий различны.

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

Выведите одно целое число — номер города, в котором Максу нужно собрать свои войска. Города нумеруются от 1 до N в порядке описания во входных данных.

Если Макс не успеет спасти от разорения ни один город, выведите -1.

Примеры

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

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

www.contester.ru