Page 128 - MATINF Nr.2

˘
128 PROBLEME DE INFORMATICA PENTRU CONCURSURI

I 30 (campanie). Un candidat la pres , edint , ia unui mare stat al lumii a intrat ˆın campania
electoral˘a. Pentru a obt , ine cˆat mai multe voturi, staful de campanie dores , te ca timpul f˘ar˘a
activitate electoral˘a s˘a fie cˆat mai mic. Acest timp se m˘asoar˘a prin distant , a pe care o parcurge
ˆın interiorul oras , elor pe drumuri f˘ar˘a aleg˘atori. Toate oras , ele alese pentru campanie au aceeas , i
structur˘a arhitectural˘a, adic˘a fiecare cont , ine cˆate dou˘a aeroporturi notate cu AS s , i AP, AS
numai pentru sosiri, iar AP numai pentru plec˘ari. Str˘azile fiec˘arui oras , sunt paralele, dou˘a
str˘azi paralele consecutive sunt legate prin drumuri f˘ar˘a aleg˘atori, punctele unde se face leg˘atura
cu acestea sunt intersect , ii. Orice dou˘a intersect , ii de pe str˘azi paralele consecutive sunt legate
printr-un drum, ˆın linie dreapt˘a. Toate str˘azile au case s , i implicit s , i aleg˘atori. AS este pe
prima strad˘a, ˆın punctul cel mai din stˆanga-jos, iar AP pe ultima strad˘a, cea mai din dreapta a
oras , ului.
Un exemplu de structur˘a arhitectural˘a pentru un oras , este prezentat mai jos.

Staful de campanie are la dispozit , ie o hart˘a cu coordonatele aeroporturilor a N oras , e s , i N
h˘art , i, cˆate una pentru fiecare oras , , cu coordonatele intersect , iilor de pe fiecare strad˘a.
Sistemul de coordonate pentru fiecare oras , are originea ˆın aeroportul pentru sosiri AS, str˘azile
fiind paralele cu axa ordonatelor, iar aeroportul pentru plec˘ari AP se afl˘a pe ultima strad˘a (cea
mai din dreapta). Axa ordonatelor este prima strad˘a (cea mai din stˆanga strad˘a).
Plecarea ˆın campanie se face dintr-un aeroport de sosiri al unui oras , , iar sfˆars , itul pe un
aeroport de plecare. Obligatoriu, candidatul trece prin toate aeroporturile.
Cerint , ˘a

Determinat , i timpul minim f˘ar˘a activitate electoral˘a ˆın campania pentru pres , edint , ie.
Date de intrare

Fis , ierul campanie.in are urm˘atoarea structur˘a:

1. pe prima linie se afl˘a N, num˘arul de oras , e;
2. pe urm˘atoarele linii se afl˘a datele pentru structura arhitectural˘a a fiec˘arui oras , : o linie cu
coordonatele aeroporturilor xAS yAS xAP yAP, separate prin cˆate un spat , iu, o linie cu
num˘arul k de str˘azi urmat de k − 1 numere cu distant , ele dintre dou˘a str˘azi consecutive,
separate prin cˆate un spat , iu de la stˆanga la dreapta, apoi k linii cu pozit , iile intersect , iilor
de pe fiecare strad˘a ˆın formatul: h y 1 y 2 . . . y h , unde y 1 , y 2 , . . . , y h sunt ordonatele
intersect , iilor. Ultima linie a datelor asociat˘a unui oras , va cont , ine ordonata aeroportului
de plec˘ari AP.

Date de ies , ire

Fis , ierul campanie.out va cont , ine un singur num˘ar natural reprezentˆand timpul minim f˘ar˘a
activitate electoral˘a ˆın campania pentru pres , edint , ie, trunchiat la 4 zecimale.