| Codeforces Global Round 11 |
|---|
| Закончено |
Заключенный хочет сбежать из тюрьмы. Тюрьма является внутренней частью выпуклого многоугольника с вершинами $$$P_1, P_2, P_3, \ldots, P_{n+1}, P_{n+2}, P_{n+3}$$$. Известно, что $$$P_1=(0,0)$$$, $$$P_{n+1}=(0, h)$$$, $$$P_{n+2}=(-10^{18}, h)$$$ и $$$P_{n+3}=(-10^{18}, 0)$$$.
Стены тюрьмы $$$P_{n+1}P_{n+2}$$$, $$$P_{n+2}P_{n+3}$$$ и $$$P_{n+3}P_1$$$ очень высокие, и заключенный не может на них взобраться. Следовательно, его единственный шанс — это достичь точки на одной из стен $$$P_1P_2, P_2P_3,\dots, P_{n}P_{n+1}$$$ и сбежать оттуда. По периметру тюрьмы находятся два охранника. Заключенный движется со скоростью $$$1$$$, в то время как охранники движутся, всегда оставаясь на периметре тюрьмы, со скоростью $$$v$$$.
Если заключенный достигает точки на периметре, где есть охранник, охранник убивает заключенного. Если заключенный достигает точки, на которую он может взобраться, и там нет охранника, то он сразу же убегает. Изначально заключенный находится в точке $$$(-10^{17}, h/2)$$$, а охранники — в точке $$$P_1$$$.
Найдите минимальную скорость $$$v$$$ такую, чтобы охранники могли гарантировать, что заключенный не сбежит (при условии, что и заключенный, и охранники будут двигаться оптимально).
Замечания:
- В любой момент охрана и заключенный могут видеть друг друга.
- Залезание на стену не занимает времени.
- Вы можете считать, что и заключенный, и охранники могут изменить направление и скорость мгновенно и что они оба имеют идеальные рефлексы (так что они могут мгновенно реагировать на то, что делает другой).
- Оба охранника могут заранее спланировать, как реагировать на передвижения заключенного.
Первая строка ввода содержит $$$n$$$ ($$$1 \le n \le 50$$$).
Следующие $$$n+1$$$ строк описывают точки $$$P_1, P_2,\dots, P_{n+1}$$$. В $$$i$$$-й из этих строк находятся два целых числа $$$x_i$$$, $$$y_i$$$ ($$$0\le x_i, y_i\le 1,000$$$) — координаты $$$P_i=(x_i, y_i)$$$.
Гарантируется, что $$$P_1=(0,0)$$$ и $$$x_{n+1}=0$$$. Гарантируется, что многоульник с вершинами $$$P_1,P_2,\dots, P_{n+1}, P_{n+2}, P_{n+3}$$$ (где $$$P_{n+2}, P_{n+3}$$$ построены так, как в условии) является выпуклым, и что никакие 3 его вершины не лежат на одной прямой.
Выведите одно действительное число — минимальную скорость $$$v$$$, которая позволяет охранникам гарантировать, что заключенный не сбежит. Ваш ответ будет считаться правильным, если его относительная или абсолютная погрешность не превысит $$$10^{-6}$$$.
2 0 0 223 464 0 749
1
3 0 0 2 2 2 4 0 6
1.0823922
4 0 0 7 3 7 4 5 7 0 8
1.130309669
5 0 0 562 248 460 610 281 702 206 723 0 746
1.148649561
7 0 0 412 36 745 180 747 184 746 268 611 359 213 441 0 450
1.134745994
