ЕЖЕГОДНАЯ ОЛИМПИАДА ПО ПРОГРАМИРОВАНИЮ В ЛИЧНОМ ЗАЧЁТЕ

11 мая регистрация участников на сайте http:\olimp.bstu.by
Дата проведения 17 мая
Время проведения с 9:00 до 12:00

 
HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > VIII ОЛИМПИАДА БрГТУ ПО ПРОГРАММИРОВАНИЮ ДЛЯ ШКОЛЬНИКОВ - очный тур > problem:


D. Вечеринка в Нью-Йорке

VIII ОЛИМПИАДА БрГТУ ПО ПРОГРАММИРОВАНИЮ ДЛЯ ШКОЛЬНИКОВ - очный тур

Start: Feb.26.2022 at 10:30:00 AM
Finish: Feb.26.2022 at 01:30:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (8)

Contest problems

• A. Подсчёт столбов
• B. В гору пойдет!
• C. Развивающие игры
• D. Вечеринка в Нью-Йорке
• E. Сладкоежка
• F. Проще простого

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 3000/3000/3000/3000 ms. Memory limit 256000/256000/256000/256000 Kb.

Вечеринка в Нью-Йорке
Вечеринка в Нью-Йорке
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
grid.in
вывод
grid.out

Скоро у Лизы день рождения! Родители долго думали, чем порадовать свою любимую дочку, и решили, что лучше всего подарить ей путешествие в Нью-Йорк. Ведь это — такой оригинальный подарок! Так как Лиза — уже самостоятельная девочка, она вполне может сама выбрать, где ей поселиться в Нью-Йорке. Однако родители очень беспокоятся за нее, поэтому они разрешили ей выбирать только из H безопасных пятизвездочных отелей.

Лиза — общительная девочка, и у неё очень много друзей. Узнав, что она будет отмечать день рождения в Нью-Йорке, друзья немедленно отправились туда и поселились в C хостелах.

Лиза по случаю дня рождения устраивает маленькую вечеринку. К сожалению, никто из её друзей не хочет пропустить очередную серию нового реалити-шоу «Home-2», но как только серия закончится, все они одновременно выйдут из своих хостелов и поедут поздравлять Лизу. Она — девочка нетерпеливая, поэтому хочет выбрать отель так, чтобы последний друг приехал к ней как можно раньше, т.е. находился как можно ближе. Так как она тоже не хочет отвлекаться от просмотра высокоинтеллектуального шоу, она попросила вас помочь ей с выбором отеля. Конечно, за это она тоже пригласит вас на вечеринку!

Как известно, Нью-Йорк представляет собой идеальную прямоугольную сетку улиц: с севера на юг тянутся N авеню, а с запада на восток — M улиц. Наличием Бродвея мы в этой задаче пренебрежем. Можно считать, что каждый объект находится в узле этой сетки (и, таким образом, однозначно задается номером авеню и номером улицы, возле пересечения которых он расположен), а два соседних узла сетки находятся на расстоянии одного километра.

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

В первой строке входных данных содержится два числа N и M — размеры города (1 ≤ N, M ≤ 109). В следующей строке содержится единственное число C — количество хостелов (1 ≤ C ≤ 105). Далее в C строках содержатся описания хостелов, каждый из них задается двумя координатами x и y (1 ≤ x ≤ N, 1 ≤ y ≤ M). В следующей строке содержится одно число H — количество отелей (1 ≤ H ≤ 105). В следующих строках содержатся описания отелей, в том же формате, что и хостелы.

Отель и хостел могут располагаться возле одного и того же перекрестка.

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

В первой строке выходных данных выведите одно число — искомое оптимальное расстояние. В следующей строке выведите номер любого из отелей, гарантирующих данное расстояние.

Примеры

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

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

10 10

2

1 1

3 3

2

1 10

4 4

6

2

 

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

www.contester.ru