Діаграма Вороного#5962

Діаграма Вороного

4 секунди

256 мегабайтів

Дуже складна

На площині потрібно обробити $Q$ запитів двох типів:

$1 x_{i} y_{i}$ 1\ x_i\ y_i — додати на площину точку $(x_{i}, y_{i} + d y)$ (x_i, y_i+dy).
$2 x_{i} y_{i}$ 2\ x_i\ y_i — знайти відстань від точки $(x_{i}, y_{i} + d y)$ (x_i, y_i+dy) до найближчої точки, яка була додана запитами першого типу.

$d y = [last_res] mod 2$ dy = [\text{last\_res}] \bmod 2 — це результат останнього виконаного запиту другого типу, а $[]$ означає округлення до найближчого цілого. До виконання хоча б одного запиту другого типу, $d y = 0$ dy=0.

Вхідні дані

У першому рядку задано одне число $Q$ ( $1 \leq Q \leq 200000$ 1 \le Q \le 200\,000) — кількість запитів. Далі йдуть $Q$ рядків, кожен з яких містить три цілі числа: $t_{i}$ t_i, $x_{i}$ x_i і $y_{i}$ y_i ( $1 \leq t_{i} \leq 2$ 1 \le t_i \le 2, $0 \leq x_{i}, y_{i} \leq 1000000$ 0 \le x_i, y_i \le 1\,000\,000) — тип запиту та координати точки. Гарантується, що для всіх $1 \leq i \leq Q - 1$ 1 \le i \le Q-1 виконується $x_{i} \leq x_{i + 1}$ x_i \le x_{i+1}, а також, що всі введені точки різні, навіть з урахуванням модифікації $d y$ . Гарантується, що перший запит завжди є запитом першого типу. Гарантується, що не виникне невизначеностей округлення, тобто дробові частини результатів усіх запитів відрізняються від $0.5$ хоча б на $1 0^{- 7}$ 10^{-7}.

Вихідні дані

Для кожного запиту другого типу виведіть в окремому рядку одне дійсне число — відстань від введеної модифікованої точки до найближчої з тих, які на цей момент були додані запитами першого типу. Потрібно, щоб значення були точними з абсолютною або відносною похибкою $1 0^{- 8}$ 10^{-8}.

Приклади

Приклад 1