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 N 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 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 Specification

The first line will contain the number N (3 \le N \le 100), the number of villages. On the next N lines there will be one integer per line, where the i^\text{th} line will contain the integer V_i, the position of the i^\text{th} village (-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

5
16
0
10
4
15

Sample Output

3.0

Explanation for Sample Output

The neighbourhoods around 0 and 16 are infinite. The neighbourhood around 4 is 5 units (2 to the left, and 3 to the right). The neighbourhood around 10 is 5.5 units (3 to the left and 2.5 to the right). The neighbourhood around 15 is 3.0 units (2.5 to the left and 0.5 to the right).


Comments


  • 0
    treeWHACKsun  commented on Feb. 3, 2024, 8:28 p.m.

    Hi!, I was using python to answer the question, and when I tried running the program locally, it works fine. However, my program only passed 1 test case, does anyone mind taking a look?: https://dmoj.ca/submission/6139460

    Very much appreciated!


    • 0
      MrWoon2010  commented on Feb. 6, 2024, 4:18 a.m.

      Didn't try out your entire code. But I suspect the error is in "for k in range (n-1) :", as you need to remove the smallest and the largest village in the sorted list. So less 2 calculations and not 1.


  • 0
    zackerburg  commented on Dec. 29, 2023, 4:12 a.m.

    i dont understand how your supposed to get the output from the given numbers. The explanation for the ouput doesn't make any sense to me can someone please explain


    • 12
      Orion222  commented on Dec. 31, 2023, 4:44 a.m.

      image

      • imagine each blue circle is a village positioned on an axis according to the input.
      • let the red background be the neighborhood of each village.
      • the neighborhood of a village is equal half the distance to the village before it plus half the distance to the village after it.
      • the first and last village have infinite neighborhoods because they don't have both a previous and next village
      • the smallest neighborhood is the village positioned at 15; 15.5 - 12.5 = 3.0

      • 0
        zackerburg  commented on Jan. 4, 2024, 3:15 a.m.

        thank you very much this clarifies things much more now!


  • 62
    SananR  commented on Feb. 18, 2018, 11: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.


    • 25
      AlanL  commented on Feb. 19, 2018, 5: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!