Знаете, в наше время довольно сложно организовать шоу с большим количеством участников и зрителей в одном месте. Тем не менее, вы не отказываетесь от своей мечты провести шоу со взрывами машин! Вы решили заменить настоящие машины радиоуправляемыми, назвать мероприятия «Шоу взрывов на радиоуправлении» и транслировать все онлайн.
Для подготовки вы нашли арену — бесконечную 2D-сетку. Вы также закупили $$$n$$$ радиоуправляемых машинок и расставили их по арене. К сожалению, эти машинки могут ехать только вперед, без возможности поворотов налево, направо или разворотов. Более того, вы направили машинки туда, куда хотите, чтобы они поехали.
Формально, для каждой машинки $$$i$$$ ($$$1 \le i \le n$$$) вы зафиксировали ее начальную позицию ($$$x_i, y_i$$$) и вектор направление ($$$dx_i, dy_i$$$). Более того, у каждой машинки есть константная скорость $$$s_i$$$ единиц в секунду. То есть после запуска машинка $$$i$$$ двигается из ($$$x_i, y_i$$$) в направлении ($$$dx_i, dy_i$$$) с константной скоростью $$$s_i$$$.
Цель вашего шоу — столкнуть две машинки как можно скорее! Вы обратили внимание, что если запускать все машинки в самом начале шоу, то довольно часто столкновений не происходит вообще. Поэтому вы решили запустить $$$i$$$-ю машинку в некоторый момент $$$t_i$$$. Вы еще не выбрали $$$t_i$$$, это еще надо решить. Обратите внимание, что $$$t_i$$$ не обязательно должно быть целым, и допустимо, чтобы $$$t_i$$$ совпадало с $$$t_j$$$ для любых $$$i, j$$$.
Шоу начинается в момент времени $$$0$$$. Шоу заканчивается, когда какие-нибудь две машинки $$$i$$$ и $$$j$$$ ($$$i \ne j$$$) сталкиваются (то есть оказываются в одной точке в одно и то же время). Длительность шоу равна времени между началом и концом.
Какое самое быстрое столкновение вы можете организовать, выбрав все $$$t_i$$$? Если возможно организовать столкновение, тогда выведите минимальную возможную длительность шоу. Иначе сообщите, что это невозможно.
В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 25000$$$) — количество машинок.
В каждой из следующих $$$n$$$ строк записаны по пять целых чисел $$$x_i$$$, $$$y_i$$$, $$$dx_i$$$, $$$dy_i$$$, $$$s_i$$$ ($$$-10^3 \le x_i, y_i \le 10^3$$$; $$$1 \le |dx_i| \le 10^3$$$; $$$1 \le |dy_i| \le 10^3$$$; $$$1 \le s_i \le 10^3$$$) — начальная позиция $$$i$$$-й машинки, ее вектор направления и ее скорость, соответственно.
Гарантируется, что все машинки начинают в различных позициях (то есть $$$(x_i, y_i) \neq (x_j, y_j)$$$ для $$$i \neq j$$$).
Выведите наименьшую возможную длительность шоу, если возможно организовать столкновение, выбрав все $$$t_i$$$. Иначе, выведите «No show :(».
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$.
Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
4 3 -1 -1 1 2 2 3 -3 -2 10 -4 2 1 -2 1 -2 -2 -1 2 4
0.585902082262898
2 -1 1 -1 1 200 1 1 1 5 200
No show :(
Картинка для первого примера:
Самое раннее возможное столкновение произойдет с машинками $$$2$$$ и $$$4$$$. Запустим машинку $$$2$$$ в $$$0$$$, машинку $$$4$$$ примерно в $$$0.096762$$$ и машинки $$$1$$$ и $$$3$$$ когда угодно. Тогда машинки $$$2$$$ и $$$4$$$ столкнутся примерно в $$$0.585902$$$. Тогда вот как поле будет выглядеть в момент столкновения:
Вот картинка для второго примера:
