Consider a map that has the following properties;
- the map is two dimensional
- the map is perfectly square with dimensions 10000000x10000000
- the map has an associated set of many features
- the map does not "wrap around"
Each feature on the map is described by a 2D coordinate in the range (0, 0) to (10000000, 10000000).
Find the most isolated feature on the map, where the "most isolated feature" is the feature that is
furthest (largest Euclidean distance) from any other feature. Because the map does not "wrap around", this should be a
direct distance across the map.
| A | |
| | |
| | 10000000
| | |
| B C | |
| E D | |
In the example above, A is the most isolated feature on the square map with edge length 10000000.
Write a program that reads in many features from standard input, and outputs the name of the most isolated
feature to standard output. The format of the input is the feature name, x coordinate and y coordinate separated by spaces.
Each feature is on a new line. There may be any number of features between 1 and 100000. The program should be fast, so the algorithm
must be better than O(n^2).
Any of the following languages are fine - C++, Python (>=2.5), C#, Java. The program shouldn't require any third-party libraries other
than the chosen language's standard libraries, and should be compilable and runnable on a modern Windows or Linux development environment
of your choice (e.g. MS Visual Studio, gcc, Eclipse etc). You should submit your program source code and any necessary makefiles or
project files required for compilation. If you write the code in C++, using C++11 features is fine.