nstructions

Closest Villages Problem

Problem: nlgn algorithm to Closest Villages Problem

More than $80\%$ of Ethiopian citizens live in rural villages. Very few of the Tigrina villages in northern Ethiopia have electricity or any form of developed travel system connecting them with the rest of the country.

This assignment is the first step in determining a cost$-$effective manner of connecting all the villages together. This is just the first step because all we are finding are the initial two villages that are the closest to each other, between which the first connecting travel lines will be placed. The Ethiopian government would like us to continue this process, continually finding the next two closest villages and using the minimum spanning tree approach, to build the complete lowest$-$cost network for connecting all the villages; however, that is beyond the scope of this assignment.

The closest villages can be found in a straightforward manner using the brute$-$force technique of comparing each village to every other village and determining the closest distance in that way. This technique is a good to confirm the correctness of other approaches, but it does not meet the nlgn performance requirement.

Input

The console input is a listing of village coordinates in a $2$D space with the origin at the southwestern most location in Tigray. Your program should read in a list of village coordinates from the console and report the names of the closest pair of villages and the distance between them.

The coordinates for the villages are in the range of $0...1,000,000.$ The village names are no more than $256$ characters and terminate with the end of the line.

To simplify handling input, the first line of the file will contain the total number of villages $(<1,000,000).$ If the distance between the closest villages is not less than $1,200,$ greater than the length or breadth of Ethiopia, output $$Infeasible$.$

Sample Input

$5$

$1039$ mekelle

$1521$ wukro

$2044$ adigrat

$4010$ axum

$5643$ debre$\_$damo

Sample Output

mekelle and adigrat are closest with a distance of $11\mathrm{.}18034$

Products

Executable: Submit the source code of a working solution. The source code should be named your last name $-03,$ then the appropriate extension for the programming language. E$.$g$.$ smith$-03.$cpp