По темам/Графы/Задачи с контестов


19. Богатырская охота

Ограничение по времени: 2 с.
Ограничение по памяти: 64 МБ

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

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

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

В первой строке входных данных содержится целое число N — количество мышей (1 ≤ N ≤ 100).

В последующих N строках содержится по четыре целых числа xi, yi, vxi и vyi — координаты и проекции скоростей на оси координат для каждой мыши (0 ≤ xi, yi, vxi, vyi ≤ 1000).

Далее в N строках по три целых числа xi, yi и vi — координаты и максимальная скорость для каждого богатыря (0 ≤ xi, yi ≤ 1000, 1 ≤ vi ≤ 10000).

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

В выходных данных должно содержаться единственное вещественное число — минимальный момент времени, в который каждый богатырь может схватить по одной мыши c абсолютной или относительной погрешностью не более 10-6

Примеры
Стандартный вводСтандартный вывод
2
0 1 0 1
1 1 0 1
0 0 20
0 0 3
0.5000000000