Задача №111537. Неспортивное ориентирование
В новой телевизионной игре участник должен попасть извне в центр системы вложенных крепостей. Каждая крепость представляет собой выпуклый многоугольник, крепости друг друга не касаются. Центральная точка имеет координаты (0, 0) и находится в самой внутренней крепости. Каждая крепость имеет несколько «дверей». Для каждой двери известно время, затрачиваемое на проход через нее. Проходить через крепостную стену вне дверей нельзя. Скорость передвижения участника вне дверей постоянна и равна 1, то есть время передвижения на расстояние S равно S.
Участник изначально находится в одной из дверей внешнего многоугольника (он сам может выбирать, в какой). Его цель — добраться до точки (0, 0) как можно быстрее. Но в игре существует следующее ограничение: когда участник вошел в какую-то дверь, в качестве следующей двери он может выбрать только такую, которая сейчас находится вне зоны его прямой видимости. Если игрок смотрит вдоль стены, то он видит находящиеся в ней двери.
Требуется определить, может ли участник добраться до финиша, и если да, то за какое минимальное время он может это сделать при оптимальном выборе стартовой двери.
В первой строке входного файла задано единственное число N (1 ≤ N ≤ 105) — количество крепостей. Далее идут N блоков данных в следующем формате: в первой строке блока содержится число K (3 ≤ K ≤ 105) — количество вершин многоугольника, описывающего крепостную стену. За ней следуют K строк, в каждой из которых записано два числа x, y — координаты соответствующей вершины. В следующей строке идет число M (1 ≤ M ≤ 105) — число дверей, расположенных на границе этого многоугольника. Затем идут M строк, каждая из которых содержит три числа x, y, t — координаты двери и время прохода через нее. Все координаты целые, по модулю не превосходящие 109. Время прохода t — целое число, 0 ≤ t ≤ 106. Общее количество вершин многоугольников, а также общее число дверей не превосходит 3·105. Гарантируется, что каждая дверь находится на границе или в вершине соответствующего многоугольника.
Первый блок соответствует внешнему многоугольнику (тому, с которого участник начинает игру), второй — вложенному в него, ..., последний блок соответствует самому внутреннему многоугольнику.
Вершины многоугольников заданы в порядке обхода против часовой стрелки. Никакие три последовательные вершины не лежат на одной прямой. Двери могут быть заданы в произвольном порядке.
Гарантируется, что при i = 1, 2, ..., N - 1 каждая точка i + 1-го многоугольника находится строго внутри i-го. Все многоугольники содержат точку (0, 0).
Выведите одно число — минимальное время, за которое участник может добраться до финиша, с абсолютной или относительной точностью 10 - 6. Если участник не может закончить игру, выведите одно число «-1» (без кавычек).
2
4
4 3
-3 3
-3 -2
4 -2
2
-3 0 3
-2 3 2
4
1 2
-1 2
-1 -1
1 -1
3
0 2 10
0 -1 4
-1 2 1
11.236067
Тесты состоят из пяти групп.
- Тест из условия, оценивается в 0 баллов.
- В тестах этой группы суммарное количество вершин и дверей не превосходит 100, а каждая крепостная стена описывается прямоугольником со сторонами, параллельными осям координат. Эта группа оценивается в 20 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы суммарное количество вершин и дверей не превосходит 100. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-ой группы. Эта группа также оценивается в 20 баллов, они начисляются только при прохождении всех тестов группы.
- В тестах этой группы суммарное количество вершин не превосходит 2000, суммарное количество дверей не превосходит 2000. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-ой и 2-й групп. Эта группа также оценивается в 20 баллов, они начисляются только при прохождении всех тестов группы.
- Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-ой, 2-ой и 3-ей групп. Каждый тест оценивается независимо от других.