Məsələlər
Мосты
Мосты
Даны два выпуклых многоугольника, каждый из которых изначально состоит из \textbf{N} вершин. Один расположен строго выше оси \textbf{OX}, другой --- строго ниже. Из многоугольников по одной удаляются вершины.
Требуется перед каждым удалением и после последнего определять длину минимального отрезка, которым можно соединить некоторую вершину первого многоугольника с некоторой вершиной второго. При этом этот отрезок не должен проходить через внутреннюю область ни одного из многоугольников.
\InputFile
Первая строка содержит число \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{100000}) --- количество вершин каждого из многоугольников. Далее \textbf{N }строк по два целых числа в каждой: \textbf{x_i}, \textbf{y_i} (\textbf{-1000000000} ≤ \textbf{x}_\{i \}≤ \textbf{1000000000}, \textbf{1} ≤ \textbf{y}_\{i \}≤ \textbf{1000000000}) --- координаты вершин первого многоугольника.
Далее \textbf{N} строк по два целых числа в каждой: \textbf{x_i}, \textbf{y_i} (\textbf{-1000000000} ≤ \textbf{x}_\{i \}≤ \textbf{1000000000}, \textbf{-1000000000} ≤ \textbf{y}_\{i \}≤ \textbf{-1}) --- координаты вершин второго многоугольника. Вершины обоих многоугольников перечислены в порядке обхода против часовой стрелки. Гарантируется, что никакие две вершины не совпадают, и никакие три вершины одного многоугольника не лежат на одной прямой. Далее \textbf{2N-2} строки по два целых числа в каждой: \textbf{n_j} и \textbf{v_j} (\textbf{1} ≤ \textbf{n_j} ≤ \textbf{2},\textbf{1} ≤ \textbf{v_j} ≤ \textbf{N}) --- означающие, что надо удалить вершину номер \textbf{v_j} из \textbf{n_j}-го многоугольника. Гарантируется, что никакая вершина не будет удалена дважды, и что после \textbf{2N-2} удалений в каждом из многоугольников останется ровно по одной вершине.
\OutputFile
\textbf{2N-1} строка, в каждой из которых одно вещественное число \textbf{d_j} --- минимальная длина отрезка, соединяющего вершины двух многоугольников и не проходящего через внутреннюю область многоугольников. \textbf{d_j} соответствует длине требуемого отрезка перед \textbf{j}-ым по порядку удалением, \textbf{d_\{2N-1\}} соответствует длине требуемого отрезка после всех удалений. Все длины должны быть правильными с абсолютной или относительной погрешностью \textbf{10^\{-8\}}.
Giriş verilənləri #1
3 1 1 4 1 2 4 0 -2 2 -4 4 -1 2 3 1 2 2 1 1 1
Çıxış verilənləri #1
2.0000000000000000 3.1622776601683795 3.1622776601683795 5.0990195135927845 8.0000000000000000