== include(page="template/taskheader" task_id="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.
!problema/campanie?campanie.bmp!
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.
Poveste şi cerinţă...
h2. 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.
Fişierul de intrare $campanie.in$ ...
h2. 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.
În fişierul de ieşire $campanie.out$ ...
h2. 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)^2^ + (y1 - y2)^2^.
* 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]$.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. campanie.in |_. campanie.out |
|3
100 0 30 0
3 10 20
2 0 20
2 10 20
3 10 30 0
0 0 10 0
2 100
1 0
2 0 10
200 0 300 0
2 100
1 0
1 0
| 97500
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. 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$.
...
== include(page="template/taskfooter" task_id="campanie") ==
