ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2005 Тур II

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Тараканьи бега

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Вот и наступил апрель. На улице набухают первые почки. Снег уже почти везде растаял. За окном все чаще и чаще раздаётся заливное щебетание птиц. Лишь на матмехе УрГУ стало видно меньше студентов. Да и в общаге совсем не видно привычных обитателей — тараканов.
«С чем связаны эти явления?» — спросите вы.
Скоро начнётся празднование Дня Математика и Механика. А вместе с ним в УрГУ будут проведены традиционные тараканьи бега. Вот и заняты все студенты сейчас тем, что тренируют своих любимцев. Каждый хочет, чтобы именно его питомец стал главным призёром соревнований и получил гордое имя «Магаз».
Правила соревнований немного необычны. Каждый круг в N точках выкладывается некоторая сладость. И одновременно к сладостям запускается M тараканов. N тараканов, добежавших первыми до сладостей, переходят в следующий тур.
Во время забега все зрители имеют уникальную возможность сделать ставки и выиграть кучу денег. Но вот организаторам тотализатора пока не весело, они не могут понять, как правильно и оперативно организовать учёт вероятностей выигрыша тараканов, чтобы получить от мероприятия максимальную прибыль. К тому же матмех — факультет не маленький, и все хотят поучаствовать.
Вам предлагается для каждого кусочка сладости найти ближайшего к нему таракана и выявить тем самым всех явных лидеров забега.

Исходные данные

В первой строке дано целое число M (1 ≤ M ≤ 100000). Далее следуют M строк, содержащих координаты тараканов в настоящий момент. (M + 2)-я строка содержит целое число N (0 ≤ N ≤ 10000). Далее в N строках записаны координаты кусочков сладости. Все координаты — действительные числа (−10000.0 ≤ x, y ≤ 10000.0). Расстояние между любыми двумя тараканами составляет не менее 10−3. Также расстояние между любыми двумя кусочками составляет не менее 10−3.

Результат

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

Пример

исходные данныерезультат
4
0 0
1 0
0 1
1 2
2
0 0
0 2
1
3 4
Автор задачи: Ден Расковалов
Источник задачи: IX Чемпионат Урала по спортивному программированию. Екатеринбург, УрГУ, 19-24 апреля 2005 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1369. Тараканьи бега