Formula 42
Flatlandiya Qran-prisini keçirmək üçün yeni Formula 42 trasının tikintisi planlaşdırılır. Məşhur tras dizayneri Herman Kilkin dəvət edildi və o, trasın çertyojlarını hazırladı. Lakin tikinti başladıqdan sonra layihədə kiçik bir problem olduğu ortaya çıxdı.
Formula 42 trası, iki tərəfdən baryerlərlə məhdudlaşdırılmış bir ərazini təmsil edir. Hər bir baryer konveks çoxbucağın sərhədi olan qapalı qırıq xəttdir. Daxili baryer tamamilə xarici baryerin içərisində yerləşir və onunla ümumi nöqtələri yoxdur. Formula 42 bolidi dairə şəklindədir. Dairənin radiusu tənzimlənmir və hesab edilir ki, yarışlar radius nə qədər böyük olsa, bir o qədər möhtəşəm olur.
Tras layihəsindəki problem ondan ibarətdir ki, Herman çertyojda xarici baryerin formasını ayrı, daxili baryerin formasını isə ayrı təsvir etmişdir. Onların qarşılıqlı yerləşməsi göstərilməmişdir. İndi trasın inşaatçıları baryerlərin qarşılıqlı yerləşməsini istədikləri kimi seçə bilərlər. Onlar baryerləri elə yerləşdirmək istəyirlər ki, yarış maksimum möhtəşəm olsun. Hər bir baryeri paralel köçürmə ilə hərəkət etdirmək olar, lakin döndərmək, əks etdirmək və ya başqa şəkildə dəyişdirmək olmaz.
Baryerlərin elə qarşılıqlı yerləşməsini seçmək tələb olunur ki, alınan trası maksimum ölçülü yarış bolidi üçün istifadə etmək mümkün olsun. Trası radiusu r olan bolidlə istifadə etmək olar, əgər belə radiuslu bolid trasda olarkən daxili baryerin ətrafında tam dövr edə bilərsə. Hərəkət zamanı bolidin heç bir nöqtəsi daxili baryerin içərisində və ya xarici baryerin xaricində olmamalıdır. Baryerlərə toxunmaq icazəlidir. Formal olaraq: qapalı baryerin içərisində olan P nöqtəsi üçün elə bir fasiləsiz qapalı əyri mövcuddur ki, P nöqtəsi bu əyrinin içərisində yerləşir və bu əyrinin hər hansı bir nöqtəsi üçün mərkəzi həmin nöqtədə olan radiusu r olan dairə xarici baryerin içərisində və daxili baryerin xaricində yerləşir, toxunmalar icazəlidir.
Hermanın planını anlamağa kömək edin və mövcud xarici və daxili baryer çertyojlarına uyğun olaraq hansı maksimum yarış bolidi radiusu üçün yarış trası tikmək mümkün olduğunu müəyyənləşdirin.
Giriş məlumatları
İki çoxbucağın təsvirini ehtiva edir, onların sərhədləri müvafiq olaraq xarici və daxili baryerlərin formalarını təyin edir.
Birinci sətirdə n (3 ≤ n ≤ 100) tam ədədi - birinci çoxbucağın zirvələrinin sayı verilir. Növbəti n sətirdə hər biri iki tam ədəd x[i] və y[i] (0 ≤ x[i], y[i] ≤ 1000) - birinci çoxbucağın zirvələrinin koordinatları verilir.
Növbəti sətirdə m (3 ≤ m ≤ 100) tam ədədi - ikinci çoxbucağın zirvələrinin sayı verilir. Növbəti m sətirdə hər biri iki tam ədəd x[i]' və y[i]' - ikinci çoxbucağın zirvələrinin koordinatları verilir (0 ≤ x[i]', y[i]' ≤ 1000).
Hər bir çoxbucağın zirvələri saat əqrəbinin əksinə istiqamətdə verilir. Çoxbucaqlar konveksdir, bir çoxbucağın heç bir üç zirvəsi bir düz xətt üzərində yerləşmir. Zəmanət verilir ki, çoxbucaqları elə paralel köçürmə ilə hərəkət etdirmək olar ki, ikinci birinci çoxbucağın tam içərisində yerləşsin və onların sərhədləri ümumi nöqtələrə malik olmasın.
Çıxış məlumatları
Bir ədəd - bolidin maksimal radiusunu çıxarın. Cavab düzgün hesab ediləcək, əgər onun mütləq və ya nisbi səhvi 10^(-6)-dan çox olmazsa.
