Punts Propers X83716


Statement
 

pdf   zip

Fes un programa que llegeix una llista de punts en el pla i fa una llista dels NN parells de punts més propers l’un de l’altre. Si els punts fóssin ciutats en un mapa, la llista representa els NN parells de ciutats més properes entre sí.

Entrada

La primera línia conté un natural N>0N > 0. Després vé un seguit de línies amb una seqüència de tripletes que representen punts en el pla bidimensional. Cada punt té un nom (un string) i dues coordenades xx i yy. És segur que NN és menor que el total de parelles de punts.

Sortida

Una llista de llargada NN, amb els parells de punts (només el nom) a menor distància. S’han d’ordenar de menor a major distància, i en cada parella el primer punt ha de ser el que apareix abans a l’entrada. Es garanteix que no hi ha parelles de punts a la mateixa distància.

Public test cases

  • Input

    3
A 0 0
B 0 .5
C 1 0
D 2 2
E 0 4.5
F 3.7 0
G -0.5 -0.8

    Output

    A B
A G
A C

  • Input

    1
A 0 0
B 1 1
C 3 3

    Output

    A B
    • Information
    Author
    Pau Fernández
    Language
    Catalan
    Other languages
    Spanish
    Official solutions
    Unknown.
    User solutions
    C++