Задача №3694. Москва 2042
К 2042 году правительство Москвы завершило очередной масштабный проект, доведя количество кольцевых автодорог до \(n\). Теперь у автомобилиста еще больше способов постоять в пробке в попытке добраться от одной точки города до другой
Компания «Giggle» планирует в своем новом продукте «Giggle Maps» реализовать возможность проложить оптимальный маршрут от одного перекрестка до другого. Карта Москвы во внутреннем формате программы представляет собой набор из \(m\) радиальных и \(n\) кольцевых магистралей, при этом некоторые из кольцевых магистралей являются односторонними.
В математической модели «Giggle» все кольцевые магистрали представляют собой концентрические окружности с центром на Красной площади и радиусами \(r_1\), \(r_2\), ..., \(r_n\). Радиальные магистрали представляют собой отрезки, один из концов каждого отрезка лежит на Красной площади, а другой — на кольцевой магистрали с максимальным радиусом. Если встать на Красной площади и смотреть на восток, то, чтобы посмотреть в направлении j-ой радиальной магистрали, нужно повернуться против часовой стрелки на \(a_j\) градусов. По каждой из радиальных магистралей можно ехать в любом направлении. Кольцевые магистрали, в свою очередь, бывают как двусторонними, так и односторонними.
Помогите компании «Giggle» найти кратчайший путь от перекрестка где пересекаются \(i_s\)-я кольцевая и \(j_s\)-я радиальная магистраль до перекрестка, где пересекаются \(i_t\)-я кольцевая и \(j_t\)-я радиальная магистраль. При этом проезжать через Красную площадь не разрешается
Первая строка входного файла содержит целые числа \(n\) и \(m\) (1 ≤ \(n\), \(m\) ≤ 100 000).
Следующие n строк описывают кольцевые магистрали. Каждая магистраль описывается целым числом \(r_i\) (1 ≤ \(r_i\) ≤ \(10^6\)) и числом 0, если магистраль является двусторонней, 1, если по ней разрешено движение только против часовой стрелки (в сторону увеличения углов радиальных магистралей) или −1, если по ней разрешено движение только по часовой стрелке.
Следующие m строк описывают радиальные магистрали. Каждая магистраль описывается одним целым числом \(A_j\) , причем \(a_j\) = \(A_j\)/\(10^6\) (0 ≤ \(A_j\) < 360 · \(10^6\)).
Затем следует две строки: первая из них содержит числа \(i_s\) и \(j_s\), а вторая — числа \(i_t\) и \(j_t\)
Выведите в выходной файл одно вещественное число: минимальное расстояние, которое придется проехать, чтобы попасть с перекрестка где пересекаются \(i_s\)-я кольцевая и \(j_s\)-я радиальная магистраль на перекресток, где пересекаются \(i_t\)-я кольцевая и \(j_t\)-я радиальная магистраль. Ваш ответ должен отличаться от правильного не больше чем на 10−4.
В приведенном примере Сережа может не выполнять четвертое задание. Остальные задания суммарно требуют 11 минут.
3 4 1 0 7 1 8 -1 0 90000000 180000000 270000000 3 1 3 2
12.99557428756427600000