Voronoi Villages
InterviewTime limit2sMemory limit512 MB
Given N village positions on a line, find the smallest finite Voronoi neighbourhood size and print it with one decimal digit.
- Level
Medium4 of 10
- Topics
- Sorting, Geometry, Implementation, Math
- Solved
- No attempts yet
Problem
In the country of Voronoi, there are N villages, located at distinct points on a straight road. Each of these villages is represented by an integer position along this road.
Each village defines its neighbourhood as all points along the road which are closer to it than to any other village. A point which is equally close to two distinct villages A and B is in the neighbourhood of A and also in the neighbourhood of B.
Each neighbourhood has a size, which is the difference between the minimum (leftmost) point in its neighbourhood and the maximum (rightmost) point in its neighbourhood.
The neighbourhoods of the leftmost and rightmost villages are defined to be of infinite size, while all other neighbourhoods are finite in size.
Determine the smallest size of any of the neighbourhoods (with exactly 1 digit after the decimal point).
Input
The first line contains the number N (3 ≤ N ≤ 100), the number of villages. On the next N lines there is one integer per line, where the ith line contains the integer Vi, the position of the ith village (−1 000 000 000 ≤ Vi ≤ 1 000 000 000). All villages are at distinct positions.
Output
Output the smallest neighbourhood size with exactly one digit after the decimal point.