Voronoy Diaqramı
Müəyyən bir müstəvidə iki növ Q sorğu verilir:
1 x_i y_i — müstəviyə (x_i, y_i+dy) nöqtəsini əlavə et.
2 x_i y_i — (x_i, y_i+dy) nöqtəsindən birinci növ sorğularla əlavə edilmiş ən yaxın nöqtəyə qədər olan məsafəni tap.
Burada dy=[last_res] mod 2 - ikinci növ sorğunun son nəticəsi, a[] isə ən yaxın tam ədədə yuvarlaqlaşdırmanı göstərir. İkinci növ sorğular başlamadan əvvəl, dy=0 olaraq qəbul edilir.
Giriş verilənləri
Birinci sətirdə bir ədəd Q (1 ≤ Q ≤ 200000) — sorğuların sayı verilir. Sonra Q sətir, hər birində üç tam ədəd: t_i, x_i və y_i (1 ≤ t_{i }≤ 2, 0 ≤ x_i, y_{i }≤ 1000000) — sorğunun növü və nöqtənin koordinatları. Bütün 1 ≤ i ≤ Q-1 üçün x_{i }≤ x_i+1 şərtinin yerinə yetirildiyi və dy modifikasiyası nəzərə alınmaqla bütün daxil edilmiş nöqtələrin fərqli olduğu təmin edilir. İlk sorğunun həmişə birinci növ sorğu olduğu təmin edilir. Yuvarlaqlaşdırma qeyri-müəyyənliyinin yaranmayacağı təmin edilir, yəni bütün sorğuların nəticələrinin kəsr hissələri 0.5-dən ən az 10^{-7} fərqlənir.
Çıxış verilənləri
Hər ikinci növ sorğu üçün ayrıca sətirdə bir real ədəd çıxarın — daxil edilmiş modifikasiya olunmuş nöqtədən həmin ana qədər birinci növ sorğularla daxil edilmiş ən yaxın nöqtəyə qədər olan məsafə. Tələb olunan dəyərlər 10^{-8} dəqiqliklə düzgün olmalıdır.