Задачі
Диаграмма Вороного
Диаграмма Вороного
На плоскости поступают \textbf{Q} запросов двух видов:
\begin{itemize}
\item \textbf{1 x_i y_i} --- добавить на плоскость точку (\textbf{x_i}, \textbf{y_i+dy})
\item \textbf{2 x_i y_i} --- найти расстояние от точки (\textbf{x_i}, \textbf{y_i+dy}) до ближайшей к ней из тех, что были добавлены запросами первого типа.
\end{itemize}
\textbf{dy=\[last_res\] mod 2} - результат последнего выполненного запроса второго типа, \textbf{а\[\]} означает округление к ближайшему целому. Перед тем, как хотя бы один запрос второго типа выполнен, \textbf{dy=0}.
\InputFile
В первой строке одно число \textbf{Q} (\textbf{1} ≤ \textbf{Q} ≤ \textbf{200000}) --- количество запросов. Далее \textbf{Q} строк по три целых числа в каждой: \textbf{t_i}, \textbf{x_i} и \textbf{y_i} (\textbf{1} ≤ \textbf{t}_\{i \}≤ \textbf{2}, \textbf{0} ≤ \textbf{x_i}, \textbf{y}_\{i \}≤ \textbf{1000000}) --- тип запроса и координаты точки. Гарантируется, что для всех \textbf{1} ≤ \textbf{i} ≤ \textbf{Q-1} выполняется \textbf{x}_\{i \}≤ \textbf{x_i+1}, а также, что все введенные точки различные даже с учетом модификации \textbf{dy}. Гарантируется, что первый запрос всегда является запросом первого типа. Гарантируется, что не возникнет неопределенностей округления, а именно, дробные части результатов всех запросов отличаются от \textbf{0.5} хотя бы на \textbf{10^\{-7\}}.
\OutputFile
Для каждого запроса второго типа в отдельной строке вывести одно вещественное число --- расстояние от введенной модифицированной точки до ближайшей из тех, которые к этому моменту поступили в запросах первого типа. Требуемые значение должны быть правильными с абсолютной или относительной погрешностью \textbf{10^\{-8\}}.
Вхідні дані #1
10 1 0 7 2 1 5 2 1 7 1 2 8 1 3 0 2 3 2 1 6 8 2 6 1 2 7 9 1 8 9
Вихідні дані #1
2.2360679774997898 1.0000000000000000 2.0000000000000000 3.0000000000000000 2.2360679774997898