Fişierul intrare/ieşire:	campanie.in, campanie.out	Sursă	Lot Botosani 2012 - Baraj 1 Seniori
Autor	Doru Popescu Anastasiu	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	2.5 sec	Limită de memorie	128384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Campanie

Un candidat la preşedinţia unui mare stat al lumii a intrat în campania electorală. Pentru a obţine cât mai multe voturi, echipa de campanie doreşte ca timpul fără activitate electorală să fie cât mai mic. Acest timp se măsoară prin distanţa pe care o parcurge mergând cu avionul între oraşe şi prin deplasarea în interiorul oraşelor pe drumuri fără alegători. Toate oraşele alese pentru campanie au aceeaşi structură arhitecturală, adică fiecare conţine câte două aeroporturi notate cu AS şi AP, AS numai pentru sosiri, iar AP numai pentru plecări. Străzile fiecărui oraş sunt paralele, două străzi paralele consecutive sunt legate prin drumuri fără alegători, punctele unde se face legătura cu acestea sunt intersecţii. Orice două intersecţii de pe străzi paralele consecutive sunt legate printr-un drum, în linie dreaptă. Toate străzile au case şi implicit şi alegători. AS este pe prima stradă, în punctul cel mai din stânga jos, iar AP pe ultima stradă, cea mai din dreapta a oraşului.

Un exemplu de structură arhitecturală pentru un oraş este prezentat mai jos.

Echipa de campanie are la dispoziţie o hartă cu coordonatele aeroporturilor a N oraşe şi N hărţi, câte una pentru fiecare oraş, cu coordonatele intersecţiilor de pe fiecare stradă.
Sistemul de coordonate pentru fiecare oraş are originea în aeroportul pentru sosiri AS, străzile fiind paralele cu axa ordonatelor, iar aeroportul pentru plecări AP se află pe ultima stradă (cea mai din dreapta). Axa ordonatelor este prima stradă (cea mai din stânga stradă).
Plecarea în campanie se face dintr-un aeroport de sosiri a unui oraş, iar sfârşitul pe acelaşi aeroport. Obligatoriu candidatul trece prin toate aeroporturile.

Determinaţi timpul minim fără activitate electorală în campania pentru preşedinţie.

Date de intrare

Fişierul de intrare campanie.in va avea următoarea structură:

• pe prima linie se află N, numărul de oraşe
• pe următoarele linii se află datele pentru structura arhitecturală a fiecărui oraş: o linie cu coordonatele aeroporturilor xAS yAS xAP yAP, separate prin câte un spaţiu, o linie cu numărul k de străzi urmat de k-1 numere cu distanţele dintre două străzi consecutive, separate prin câte un spaţiu de la stânga la dreapta, apoi k linii cu poziţiile intersecţiilor de pe fiecare stradă în formatul: h y1 y2 …yh, unde y1, y2, …, yh sunt ordonatele intersecţiilor.

Date de ieşire

Fişierul de iesire campanie.out va conţine un singur număr natural reprezentând timpul minim fără activitate electorală în campania pentru preşedinţie.

Restricţii

• N este număr natural proprietatea că 2 ≤ N ≤ 18
• Distanţa parcursă între două oraşe sau două intersecţii de coordonate (x1,y1) şi (x2,y2) se defineşte ca fiind (x1 - x2)² + (y1 - y2)².
• Numărul de străzi dintr-un oraş ≤ 1000.
• Numărul de intersecţii de pe o stradă ≤ 1000.
• Distanţele dintre două străzi consecutive ale aceluiaşi oraş ≤ 1000.
• Toate ordonatele intersecţiilor dintr-un oraş şi cea a aeroportului pentru plecări sunt ≤ 10000.
• Coordonatele pe harta cu oraşe sunt numere întregi din intervalul [-10000, 10000].

Exemplu

Explicaţie

Ordinea oraşelor în care va ajunge candidatul este 1, 2, 3. În oraşul 1 timpul fără activitate electorală va fi 500, în oraşul 2 va fi 10000, iar în oraşul 3 va fi 10000.

Cum se trimit solutii?