Задача №3695. Морской бой
Недавно Вова купил настольную игру «Морской бой». Это пошаговая игра для двух игроков, действие которой разворачивается на просторах бесконечного клетчатого поля. У каждого из игроков есть свой флот, который состоит из нескольких кораблей. Каждый корабль занимает ровно одну клетку поля. Флот каждого из игроков движется по полю с постоянной скоростью — все корабли i-ого игрока каждые ti шагов перемещается на вектор (∆\(x_i\), ∆\(y_i\)). Таким образом, корабли i-ого игрока перемещаются по полю на шагах с номерами 1, \(t_i\) + 1, 2 · \(t_i\) + 1 и.т.д.
Требуется написать программу, которая по заданному расположению кораблей до первого шага игры и их скоростям вычисляет номер шага, на котором будет ближайший бой.
Требуется написать программу, которая по заданному расположению кораблей до первого шага игры и их скоростям вычисляет номер шага, на котором будет ближайший бой.
Входной файл содержит описания флотов двух игроков. Описание флота состоит из нескольких строк. Первая строка описания содержит четыре целых числа: \(m_i\) (1 ≤ \(m_i\) ≤ 10000) — число кораблей во флоте \(i\)-ого игрока, а так же \(t_i\) (1 ≤ \(t_i\) ≤ 10), ∆\(x_i\), ∆\(y_i\) (|∆\(x_i\)|, |∆\(y_i\)| ≤ 10).
Затем следуют \(m_i\) строк, каждая из которых содержит по два целых числа — \(x_j\) и \(y_j\) (|\(x_j\)|, |\(y_j\) | ≤ \(10^9\)) — координаты кораблей во флоте до первого шага игры.
Никакие два корабля, описанные во входном файле, не находятся в начальный момент времени в одной и той же клетке.
В выходной файл необходимо вывести номер шага, на котором произойдет первый бой. Если бой никогда не состоится, выведите в выходной файл -1
3 1 1 0 2 0 1 1 1 -1 2 2 -2 0 8 1 8 2
3
1 1 2 0 1 1 1 1 -2 0 2 2
-1