Metrou 4

Metrou4

== include(page="template/taskheader" task_id="metrou4") ==

Acum patru ani, Jones a fost ales primarul unui oraş important. Între timp, Jones nu a reuşit să  implementeze nici una din promisiunile sale electorale. Pentru a nu pierde noile alegeri a decis să propună un plan pentru a conecta prin linii de metrou cele mai importante N locaţii din oraş. Principala problemă intâmpinată este că robotul achiziţionat fară licitaţie pentru a realiza tuneluri in subteran poate să se mişte doar in linii drepte, spre nord, sud, est sau vest.

Acum patru ani, Jones a fost ales primarul unui oraş important. Între timp, Jones nu a reuşit să implementeze nici una din promisiunile sale electorale. Pentru a nu pierde noile alegeri a decis să propună un plan pentru a conecta prin linii de metrou cele mai importante N locaţii din oraş. Principala problemă intâmpinată este că robotul achiziţionat fară licitaţie pentru a realiza tuneluri in subteran poate să se mişte doar in linii drepte, spre nord, sud, est sau vest.

Costul unui plan este dat de distanţa totală a tunelurilor săpate. Jones vă cere să îl ajutaţi să stabilească un plan de cost minim astfel incât să se poată ajunge din orice locaţie in orice altă locaţie folosind metroul.
h2. Date de intrare

Datele de intrare se citesc din fisierul “metrou4.in”.

Datele de intrare se citesc din fişierul “metrou4.in”.

Pe prima linie se află numărul de teste, T. Fiecare test va începe cu numărul de locaţii N. Următoarele N linii sunt de forma X Y, unde X şi Y sunt numere întregi, reprezentând coordonatele unei locaţii.
h2. Date de ieşire

h2. Restricţii

* 1 ≤ T ≤ 10
* 1 ≤ N ≤ 200.000

* 1 ≤ T ≤ 12
* 1 ≤ N ≤ 150.000

* 0 ≤ X,Y ≤ 1.000.000.000
* Se poate săpa un tunel între oricare două locaţii.

* Fiecare tunel este distinct, nu se poate refolosi o secţiune a unui tunel săpat anterior pentru a conecta două locaţii.

h2. Exemplu
table(example). |_. metrou4.in |_. metrou4.out |

| 2

| 3
3
0 0
1 1
0 2

4
0 0
1 1

2 2
1 1
0 0

| 3

| 4
3

10
|

h3. Explicaţie
...

== include(page="template/taskfooter" task_id="metrou4") ==