Körpülər
Verilmiş iki qabarıq çoxbucaqlı var, hər biri N zirvədən ibarətdir. Biri OX oxunun tam yuxarısında, digəri isə tam aşağısında yerləşir. Çoxbucaqlardan bir-bir zirvələr silinir.
Hər silmədən əvvəl və sonuncudan sonra birinci çoxbucaqlının bəzi zirvəsini ikinci çoxbucaqlının bəzi zirvəsi ilə birləşdirə biləcək minimal uzunluqlu parça tapmaq tələb olunur. Bu parça heç bir çoxbucaqlının daxili sahəsindən keçməməlidir.
Giriş verilənləri
Birinci sətir N (3 ≤ N ≤ 100000) — hər çoxbucaqlının zirvələrinin sayını göstərir. Ardınca N sətir gəlir, hər birində iki tam ədəd: x_i, y_i (-1000000000 ≤ x_{i }≤ 1000000000, 1 ≤ y_{i }≤ 1000000000) — birinci çoxbucaqlının zirvələrinin koordinatları.
Sonra N sətir gəlir, hər birində iki tam ədəd: x_i, y_i (-1000000000 ≤ x_{i }≤ 1000000000, -1000000000 ≤ y_{i }≤ -1) — ikinci çoxbucaqlının zirvələrinin koordinatları. Hər iki çoxbucaqlının zirvələri saat əqrəbi istiqamətinin əksinə sıralanıb. Heç bir iki zirvənin üst-üstə düşmədiyi və bir çoxbucaqlının heç bir üç zirvəsinin eyni düz xətt üzərində olmadığı təmin edilir. Daha sonra 2N-2 sətir gəlir, hər birində iki tam ədəd: n_j və v_j (1 ≤ n_j ≤ 2, 1 ≤ v_j ≤ N) — n_j-ci çoxbucaqlının v_j nömrəli zirvəsinin silinməli olduğunu göstərir. Heç bir zirvənin iki dəfə silinməyəcəyi və 2N-2 silmədən sonra hər çoxbucaqlıda yalnız bir zirvənin qalacağı təmin edilir.
Çıxış verilənləri
2N-1 sətir, hər birində bir həqiqi ədəd d_j — iki çoxbucaqlının zirvələrini birləşdirən və çoxbucaqların daxili sahəsindən keçməyən minimal uzunluqlu parçanın uzunluğu. d_j j-ci silmədən əvvəl tələb olunan parçanın uzunluğuna, d_{2N-1} isə bütün silmələrdən sonra tələb olunan parçanın uzunluğuna uyğun gəlir. Bütün uzunluqlar 10^{-8} dəqiqliklə düzgün olmalıdır.