În regatul XLand orasele erau înconjurate de ziduri în forma de poligoane convexe. Împaratul a dispus construirea unui drum de legatura directa între capitala si un alt oras dat. Fiecare extremitate a drumului poate fi orice punct situat pe zidul orasului, respectiv capitalei. Lungimea drumului este distanta dintre extremitatile sale.
Cerinta
Determinati cel mai scurt drum dintre capitala si orasul dat.
Date de intrare
Fisier de intrare: DRUM.IN
Linia 1: K1
· numar natural nenul, reprezentând numarul de colturi
ale zidurilor capitalei;
Linia 2: x1 y1
x2 y2 ... xK1 yK1
· K1 perechi de numere întregi, separate prin câte un spatiu, reprezentând
coordonatele vârfurilor zidurilor capitalei;
Linia 3: K2
· numar natural nenul, reprezentând numarul de colturi
ale zidurilor orasului dat;
Linia 4: x1 y1
x2 y2 ... xK2 yK2
· K2 perechi de numere întregi, separate prin câte un spatiu, reprezentând
coordonatele vârfurilor zidurilor acestui oras.
Date de iesire
Fisier de iesire: DRUM.OUT
Linia 1: x1 y1
x2 y2
· patru numere reale trunchiate la 4 zecimale, separate
prin câte un spatiu, reprezentând extremitatile drumului de legatura respectiv.
· 2 Ł K1,K2 Ł 20
· Coordonatele vârfurilor zidurilor ce înconjoara orasul,
respectiv capitala sunt numere întregi apartinând intervalului [-100,100] si sunt date fie în ordinea deplasarii acelor de ceasornic,
fie în sens invers deplasarii acelor de ceasornic.
· Capitala si orasul nu au nici un punct comun (nu au
puncte interioare comune si nu au puncte comune pe zidurile lor).
Exemplu
DRUM.IN
4
3 4 3 2 5 2 5 4
4
8 3 8 6 11 6 11 3
DRUM.OUT
5.0000 3.5000 8.0000 3.5000