| Tinkoff Challenge - Elimination Round |
|---|
| Закончено |
Аналитик Игорь задремал на работе, и ему приснился сон. Во сне у Игоря на рабочем столе завелось много компьютерных мышей, поэтому он купил себе мышеловку.
Рабочий стол можно представить как бесконечную плоскость, тогда мышеловка представляет из себя прямоугольник, стороны которого параллельными осям координат, противоположные углы которого находятся в точках с координатами (x1, y1) и (x2, y2).
Игорь хочет поймать всех мышей. Анализируя их поведение, Игорь выяснил, что каждая мышь ползет прямолинейно с постоянной скоростью, скорость мыши номер i равна (vix, viy), что означает, что координата x позиции мыши увеличивается за секунду на vix, а координата y — на viy. Изначально мышеловка поднята, и мыши могут свободно передвигаться по столу. Игорь может в любой момент времени опустить мышеловку, при этом он поймает всех мышей, оказавшихся строго внутри мышеловки.
Игорь очень трудолюбивый и даже во сне трудится на своей работе, поэтому он просит вас написать программу, которая по заданным координатам мышеловки, позициям мышей в начальный момент времени и их скоростям вычислит ближайший момент времени, в который ему удастся поймать всех мышей. Обратите внимание, что Игорь может опустить мышеловку только один раз.
Первая строка содержит одно целое число n (1 ≤ n ≤ 100 000) — количество компьютерных мышей у Игоря в офисе.
Вторая строка содержит четыре целых числа x1, y1, x2 и y2 (0 ≤ x1 ≤ x2 ≤ 100 000), (0 ≤ y1 ≤ y2 ≤ 100 000) — координаты противоположных углов мышеловки.
Следующие n строк содержат информацию о мышах.
В i-й из этих строк содержится четыре целых числа rix, riy, vix и viy, (0 ≤ rix, riy ≤ 100 000, - 100 000 ≤ vix, viy ≤ 100 000), где (rix, riy) — позиция мыши в начальный момент времени, а (vix, viy) — ее скорость.
В единственной строке выведите минимальное неотрицательное t такое, что если Игорь опустит мышеловку в момент времени t секунд, то все компьютерные мыши окажутся строго внутри мышеловки. Если такого t не существует, выведите -1.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри b. Ваш ответ будет засчитан, если 
.
4
7 7 9 8
3 5 7 5
7 5 2 4
3 3 7 8
6 6 3 2
0.57142857142857139685
4
7 7 9 8
0 3 -5 4
5 0 5 4
9 9 -1 -6
10 5 -7 -10
-1
Ниже приведена иллюстрация первого примера.
Точки A, B, C, D - начальные положение мышей, отрезками показан их путь.
Тогда в первый момент времени, в котором все точки будут находиться в прямоугольнике, прямоугольник будет выглядеть следующим образом:
Иллюстрация второго примера выглядит так:
Как видно на изображении, мыши A, D и B никогда не попадут в прямоугольник.
