Giardinaggio

Pippo ha deciso di spendere il proprio tempo libero facendo giardinaggio.
Poiché il numero di fiori piantati nelle sue aiuole gli pare eccessivo, decide di ridurne il numero eliminando quelli tra loro più vicini.
A tale scopo, essendo appassionato di informatica, decide di scrivere un programma che gli permetta di risolvere il problema.

Di ogni fiore viene identificata la posizione e questa viene memorizzata in un file indicando le coordinate, in centimetri, rispetto l’angolo in basso a sinistra dell’aiuola; ogni posizione è contenuta in una riga diversa del file e codificata con due numeri interi separati da uno spazio.
Oltre alle righe che contengono le posizioni dei fiori, il file contiene anche, nella prima riga, il numero di fiori che deve essere eliminato.

In sostanza il programma deve cercare la coppia di fiori con distanza minima ed eliminare, dei due, il fiore più in alto (cioè quello la cui ordinata è maggiore); ripetere, quindi, l’operazione tante volte quanti sono i fiori da eliminare.
Nel caso in cui l’ordinata dei due fiori fosse uguale, il fiore da eliminare è quello con ascissa maggiore.

Dati di input

I dati di ingresso sono contenuti nel file input.txt che contiene:

• nella prima riga, un numero intero che rappresenta il numero di fiori da eliminare;
• dalla seconda riga al termine, coppie di numeri interi separati da uno o più spazi bianchi, il primo rappresenta l’ascissa ed il secondo l’ordinata della piantina

Dati di output

Il risultato deve essere scritto nel file di testo output.txt indicando le coordinate dei punti eliminati nello stesso formato del file in ingresso (esclusa la prima riga).
I punti devono essere ordinati, in modo crescente, rispetto all’ascissa, e nel caso in cui avessero la stessa ascissa, rispetto l’ordinata.

Assunzioni

1. Non ci sono due o più fiori esattamente nello stesso punto;
2. la distanza è calcolata usando la formula euclidea;
3. il numero di piante da eliminare, indicato nel file di ingresso, è sempre minore o uguale al numero di piante contenute nello stesso file;
4. il file di ingresso contiene almeno due piante;
5. l’aiuola ha dimensioni 1000×1000 cm.

Esempio di input e output