CCC '18 S1 - Voronoi Villages

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Canadian Computing Competition: 2018 Stage 1, Senior #1

In the country of Voronoi, there are NN villages, located at distinct points on a straight road. Each of these villages will be 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 AA and BB is in the neighbourhood of AA and also in the neighbourhood of BB.

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 Specification

The first line will contain the number NN (3 \le N \le 100)(3 \le N \le 100), the number of villages. On the next NN lines there will be one integer per line, where the i^\text{th}i^\text{th} line will contain the integer V_iV_i, the position of the i^\text{th}i^\text{th} village (-1\,000\,000\,000 \le V_i \le 1\,000\,000\,000)(-1\,000\,000\,000 \le V_i \le 1\,000\,000\,000). All villages are at distinct positions.

Output Specification

Output the smallest neighbourhood size with exactly one digit after the decimal point.

Sample Input


Sample Output


Explanation for Sample Output

The neighbourhoods around 00 and 1616 are infinite. The neighbourhood around 44 is 55 units (22 to the left, and 33 to the right). The neighbourhood around 1010 is 5.55.5 units (33 to the left and 2.52.5 to the right). The neighbourhood around 1515 is 3.03.0 units (2.52.5 to the left and 0.50.5 to the right).


  • -1
    harry7557558  commented on Feb. 29, 2020, 3:06 a.m.

    This problem can be solved without using float point.

  • 4
    KousakaHonoka  commented on Jan. 30, 2019, 9:54 p.m.

    I spent 4 hours on figuring out the mechanics of outputting and inputting. Damn YES!

  • 5
    IanHu  commented on Dec. 29, 2018, 3:40 p.m. edited

    I spent 10 min trying to figure out why 4 is 5 units (2 to the left, and 3 to the right) and then find that "5" in the sample input is NOT a villiage.... I am soooo stupid

  • 45
    SananR  commented on Feb. 18, 2018, 6:53 p.m.

    For those who are constantly getting 6/15, make sure that your output isn't in scientific notation, took me a bit to figure that out on the CCC.

    • 18
      AlanL  commented on Feb. 19, 2018, 12:34 p.m.

      It says that in the editorial as well, but it probably only occurs in some languages. Thanks anyways for that useful info!