Tortun kəsilməsi#2522

Tortun kəsilməsi

3 saniyə
256 meqabayt
Çox çətin

Paşa ad günü üçün üzərində iki növ bəzək olan tort alıb: kremli güllər və albalılar. O, ən azı bir kremli gül olan, lakin heç bir albalısı olmayan bir tort parçası kəsmək istəyir.

Tortu yuxarıdan baxanda kvadrat kimi təsəvvür edin. Əgər küncləri (-10^6, -10^6) və (10^6, 10^6) olan bir düzbucaqlı Karteziya koordinat sistemi qurulsa (orijini tortun mərkəzindədir və oxlar kvadratın tərəflərinə paraleldir), bütün kremli güllər və albalılar tam olaraq bu kvadratın içərisində yerləşir.

Bir parça kəsmək üçün, Paşa bir düz xətt boyunca bir kəsik etmək istəyir. Kəsmə asan olsun deyə, kəsən düz xətt ilə oxu arasındakı bucaq mümkün qədər kiçik olmalıdır.

Sənin tapşırığın — Paşanın təsvir olunan qayda ilə tortu kəsib-kəsə bilmədiyini müəyyən etmək və əgər mümkündürsə, kəsən düz xətt ilə oxu arasındakı minimal bucağı tapmaqdır.

Əgər kremli gül və ya albalı tam olaraq kəsik xəttinin üstündə yerləşirsə, Paşa kəsiyi elə apara bilər ki, həmin gül və ya albalı istənilən tərəfdə qalsın (uyğun olaraq).

Şəkildə birinci nümunə üçün optimal kəsik nöqtəli xətlə göstərilib. Qırmızı nöqtələr gülləri, mavi nöqtələr isə albalıları göstərir.

Şəkil: Birinci nümunə üçün güllərin və albalıların yerləşməsi

Giriş

Birinci sətirdə tam ədəd (1 \le n \le 100000) — kremli güllərin sayı verilir. Sonrakı sətirin hər birində iki tam ədəd, bir kremli gülün koordinatları verilir.

Sonra bir sətirdə tam ədəd (1 \le m \le 100000) — albalıların sayı verilir. Sonrakı sətirin hər birində iki tam ədəd, bir albalının koordinatları verilir.

Heç bir kremli gül ilə albalı eyni nöqtədə yerləşmir. Bütün güllərin və albalıların koordinatlarının modulu 10^6-dan kiçikdir.

Çıxış

Əgər tortu göstərilən şəkildə kəsmək qeyri-mümkündürsə, **Impossible** çap et.

Əks halda, oxu ilə kəsən düz xətt arasında minimal bucağı radianla, azı 10^{-4} dəqiqliklə çap et.

Nümunələr

Nümunə 1

Loading
Loading