Çoxbucaqlıların bölünməsi
Müəyyən bir müstəvidə iki qabarıq çoxbucaqlı fiqur verilib. Bu fiqurlar elə yerləşdirilib ki, onların zirvələri üst-üstə düşmür və konturlarında dəqiq 2 kəsişmə nöqtəsi var.
Müstəvini istənilən şəkildə bir düz xətt ilə bölək. Düz xəttin bir tərəfindəki yarım müstəvini birinci fiqura, digər tərəfindəki yarım müstəvini isə ikinci fiqura uyğun hesab edəcəyik. Bölünmə qüsuru anlayışını müəyyən edək - birinci fiqurun ikinci fiqurun yarım müstəvisində yerləşən sahəsi ilə ikinci fiqurun birinci fiqurun yarım müstəvisində yerləşən sahəsinin cəmi. Yarım müstəvilərin fiqurlara iki mümkün uyğunluğundan qüsurun daha az olduğu uyğunluğu seçəcəyik.
Məsələn, şəkildə çoxbucaqlıların müəyyən bir bölünməsini təyin edən bir düz xətt göstərilib. Bu bölünmənin qüsurunun qiymətləndirilməsi (iki uyğunluq halı): (D) + (C + E) və (A + D) + (B + C). Şəkildən göründüyü kimi, D + C + E daha azdır, beləliklə, ümumilikdə, bu düz xətt ilə yaradılan bölünmənin qüsurunun qiymətləndirilməsi D + C + E olur.
İki çoxbucaqlı verildikdə, qüsuru ən az olan bölünməni yaradan düz xətti tapan proqram yazın.
Giriş verilənləri
Birinci sətir bir tam ədəd N (3 ≤ N ≤ 20) - birinci çoxbucaqlının zirvələrinin sayını ehtiva edir. Növbəti N sətir tam ədədlər cütlərini ehtiva edir - birinci çoxbucaqlının zirvələrinin koordinatları keçid qaydasında. (N + 2) -ci sətir faylda M (3 ≤ M ≤ 20) - ikinci çoxbucaqlının zirvələrinin sayını ehtiva edir. Növbəti M sətir onun koordinatlarını birinci çoxbucaqlı üçün olduğu kimi müəyyən edir. Nöqtələrin koordinatları müsbətdir və 1000-i keçmir.
Çıxış verilənləri
Bir sətirdə iki nöqtənin koordinatlarını - qüsuru ən az olan bölünməni (düz xətti) dəqiq müəyyən edən iki nöqtənin koordinatlarını çıxarın. Rəqəmləri bu qaydada çıxarın: x_1 y_1 x_2 y_2. Koordinatları 10^{-3} dəqiqliyi ilə çıxarın. Nöqtələrin koordinatları müsbət olmalı və 1000-i keçməməlidir.