Мосты
Даны два выпуклых многоугольника, каждый из которых изначально состоит из N вершин. Один расположен строго выше оси OX, другой — строго ниже. Из многоугольников по одной удаляются вершины.
Требуется перед каждым удалением и после последнего определять длину минимального отрезка, которым можно соединить некоторую вершину первого многоугольника с некоторой вершиной второго. При этом этот отрезок не должен проходить через внутреннюю область ни одного из многоугольников.
Входные данные
Первая строка содержит число N (3 ≤ N ≤ 100000) — количество вершин каждого из многоугольников. Далее N строк по два целых числа в каждой: x_i, y_i (-1000000000 ≤ x_{i }≤ 1000000000, 1 ≤ y_{i }≤ 1000000000) — координаты вершин первого многоугольника.
Далее N строк по два целых числа в каждой: x_i, y_i (-1000000000 ≤ x_{i }≤ 1000000000, -1000000000 ≤ y_{i }≤ -1) — координаты вершин второго многоугольника. Вершины обоих многоугольников перечислены в порядке обхода против часовой стрелки. Гарантируется, что никакие две вершины не совпадают, и никакие три вершины одного многоугольника не лежат на одной прямой. Далее 2N-2 строки по два целых числа в каждой: n_j и v_j (1 ≤ n_j ≤ 2,1 ≤ v_j ≤ N) — означающие, что надо удалить вершину номер v_j из n_j-го многоугольника. Гарантируется, что никакая вершина не будет удалена дважды, и что после 2N-2 удалений в каждом из многоугольников останется ровно по одной вершине.
Выходные данные
2N-1 строка, в каждой из которых одно вещественное число d_j — минимальная длина отрезка, соединяющего вершины двух многоугольников и не проходящего через внутреннюю область многоугольников. d_j соответствует длине требуемого отрезка перед j-ым по порядку удалением, d_{2N-1} соответствует длине требуемого отрезка после всех удалений. Все длины должны быть правильными с абсолютной или относительной погрешностью 10^{-8}.