Page 107 - REVISTA MATINF Nr. 5

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 107

Exemplu

pavari.in pavari.out
2 11

Timp maxim de execut , ie: 0.1 sec./test. Memorie total˘a disponibil˘a 2 MB.

Doru Anastasiu Popescu, Pites , ti

ˆ
I 74 (drum). In regatul XLand oras , ele erau ˆınconjurate de ziduri ˆın form˘a de poligoane convexe.
ˆ
Imp˘aratul a dispus construirea unui drum de leg˘atur˘a direct˘a ˆıntre capital˘a s , i un alt oras , dat.
Fiecare extremitate a drumului poate fi orice punct situat pe zidul oras , ului, respectiv capitalei.
Lungimea drumului este distant , a dintre extremit˘at , ile sale.

Cerint , ˘a
Determinat , i cel mai scurt drum dintre capital˘a s , i oras , ul dat.

Date de intrare

Fis , ierul de intrare drum.in cont , ine:
Linia 1: K1 - num˘ar natural nenul, reprezentˆand num˘arul de colt , uri ale zidurilor capitalei;
Linia 2: x 1 y 1 x 2 y 2 ... x K1 y K1 - K1 perechi de numere ˆıntregi, separate prin cˆate un spat , iu,
reprezentˆand coordonatele vˆarfurilor zidurilor capitalei;
Linia 3: K2 - num˘ar natural nenul, reprezentˆand num˘arul de colt , uri ale zidurilor oras , ului dat;
Linia 4: x 1 y 1 x 2 y 2 ... x K2 y K2 - K2 perechi de numere ˆıntregi, separate prin cˆate un spat , iu,
reprezentˆand coordonatele vˆarfurilor zidurilor acestui oras , .

Date de ies , ire
Fis , ierul de ies , ire drum.out va cont , ine o singur˘a linie cu numerele:
x1 y1 x2 y2 - patru numere reale trunchiate la 4 zecimale, separate prin cˆate un spat , iu,
reprezentˆand extremit˘at , ile unui drum minim.

Restrict , ii s , i preciz˘ari
• 1 ≤ K1, K2 ≤ 20
• Coordonatele vˆarfurilor zidurilor ce ˆınconjoar˘a oras , ul, respectiv capitala sunt numere
ˆıntregi apart , inˆand intervalului [-100,100] s , i sunt date fie ˆın ordinea deplas˘arii acelor de
ceasornic, fie ˆın sens invers deplas˘arii acelor de ceasornic
• Capitala s , i oras , ul nu au niciun punct comun (nu au puncte interioare comune s , i nu au
puncte comune pe zidurile lor)

Exemplu

drum.in drum.out
4 5 3.5 8 3.5
3 4 3 2 5 2 5 4
4
8 3 8 6 11 6 11 3

Timp maxim de execut , ie: 0.1 sec./test. Memorie total˘a disponibil˘a 2 MB.

Doru Anastasiu Popescu, Pites , ti