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

1849. Охота на зайцев 2

Ограничение времени: 4.0 секунды
Ограничение памяти: 64 МБ
Хороший охотник убивает одним выстрелом двух зайцев. Но чтобы стать лучшим охотником в мире, вам нужно научиться убивать максимально возможное количество зайцев одним выстрелом. В этом вам поможет программа Rabbit Hunt 2. Программа считает всех зайцев точками на плоскости. Ей на вход подаются координаты n зайцев, после чего она генерирует q возможных вариантов выстрела и выбирает из них тот, который убьёт наибольшее количество зайцев. Выстрел задаётся точкой, где должен стоять охотник, и направляющим вектором луча, по которому летит пуля. Считается, что выстрел убивает всех зайцев, лежащих на этом луче, в том числе зайца, расположенного в той же точке, что и охотник.
Генератор позиций использует числа ax, bx, ay, by, avx, bvx, avy, bvy. Координаты охотника в первой позиции — (x1y1), а направление первого выстрела — (vx1vy1). Координаты охотника и направляющий вектор для i-го выстрела (i > 1) вычисляются по формулам:
Problem illustration
Проблема в том, что программы Rabbit Hunt 2 ещё не существует. Вам предстоит её написать.

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

В первой строке записано целое число n (1 ≤ n ≤ 10 000) — количество зайцев. В каждой из следующих n строк через пробел записаны координаты очередного зайца. Координаты — целые числа, по модулю не превосходящие 10 000. Никакие два зайца не расположены в одной точке. В следующей строке записано целое число q (1 ≤ q ≤ 106) — количество генерируемых позиций. В следующей строке через пробел записаны целые числа x1, y1, vx1, vy1 (−10 000 ≤ x1, y1 ≤ 10 000; −10 ≤ vx1, vy1 ≤ 10). В последней строке через пробел записаны неотрицательные целые числа ax, bx, ay, by, avx, bvx, avy, bvy. Все эти числа не превосходят 105. Гарантируется, что ни в одной из первых q позиций направляющий вектор выстрела не будет нулевым.

Результат

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

Пример

исходные данныерезультат
4
0 0
2 0
3 0
2 2
3
-1 -1 1 0
1 0 1 1 1 0 1 0
2 3
Автор задачи: Алексей Самсонов
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2010