URI Online Judge | 1234

As Relíquias da Morte

Por Leandro Zatesko, UFFS BR Brazil

Timelimit: 2

A cultura dos povos nativos do Brasil está morrendo! Enquanto que se estima que no séc. XV havia mais de mil povos indígenas no Brasil, hoje há o registro de apenas 215 povos. Recentemente, foram descobertas na região do oeste catarinense relíquias fósseis atribuídas a um povo indígena extinto. As relíquias tratam-se provavelmente de bases de muros de edificações. A figura abaixo ilustra algumas relíquias encontradas representando cada relíquia por um segmento de reta.

Agora, o Governo quer transformar todas as terras em que estão as relíquias em área de preservação ambiental. Para facilitar o trabalho dos arqueólogos, o governo também construirá trilhas, cada uma conectando duas relíquias. A intenção é construir o mínimo possível de trilha, a fim de que o impacto ambiental seja o menor possível, mas que haja caminho entre quaisquer duas trilhas. A figura abaixo ilustra uma maneira de construir trilhas entre as relíquias da figura acima de modo a minimizar a soma total dos comprimentos das trilhas.

Entrada

A primeira linha da entrada é constituída unicamente por um inteiro N (1 ≤ N ≤ 103), o qual representa o número de relíquias encontradas. Cada uma das N linhas seguintes descreve uma relíquia através de quatro inteiros, xA, yA, xB e yB (0 ≤ xA, yA, xB, yB ≤ 104), os quais representam as coordenadas dos extremos (xA, yA) e (xB, yB) do segmento de reta, de comprimento não necessariamente positivo, que representa a relíquia.

Saída

Imprima uma linha constituída unicamente por um valor que representa a soma total ótima dos comprimentos das trilhas que conectam as relíquias. Como a empresa contratada para construir as trilhas cobra por unidade inteira de trilha construída, se o valor não for inteiro arredonde-o para cima.

Exemplos de Entrada Exemplos de Saída

7
0 0 3 2
1 12 1 17
9 4 7 7
13 1 18 1
16 14 13 11
16 20 21 15
16 19 21 19

31

7
0 0 0 2
0 4 0 6
2 6 4 6
6 6 8 6
8 4 8 2
8 0 6 0
4 0 2 0

12