CCC '18 S1 - Voronoi Villages - DMOJ: Modern Online Judge

CCC '18 S1 - Voronoi Villages

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$ ~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$ ~A~ and $B$ ~B~ is in the neighbourhood of $A$ ~A~ and also in the neighbourhood of $B$ ~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$ ~N~ $(3 \le N \le 100)$ ~(3 \le N \le 100)~, the number of villages. On the next $N$ ~N~ lines there will be one integer per line, where the $i^\text{th}$ ~i^\text{th}~ line will contain the integer $V_i$ ~V_i~, the position of the $i^\text{th}$ ~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

Sample Output

3.0

Explanation for Sample Output

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

Comments

-3

arvinaz commented on Oct. 15, 2022, 8:57 p.m.

To further clarify the output:

The neighbourhood around is units (2 to the left, and 3 to the right)

This basically means that the halfway point between 0 and 4 is 2, and 4 to 10 is 7. Thus the neighborhood starts at position 2 and ends at 7, which brings it to 5 units overall (unrelated to N = 5, first sample input).

11

ivan79 commented on June 3, 2022, 7:06 a.m.

You can down vote me as much as you want, but this problem is described in extremely vague terms. It took me forever to understand that we need to sort the villages before we do any logic on them. Seriously how hard is it to say that villages are sorted in the explained example!

-5

ReverseEMF commented on June 16, 2022, 5:55 p.m. ← edit 2 →

The need to sort is obvious to one with experience. So, the validity of your complaint depends on the expected level of contestant skill in these contests.

This comment is hidden due to too much negative feedback. Show it anyway.

4

johnmagee commented on June 29, 2022, 9:32 p.m.

Whether the need to sort or not is obvious that doesn't bely that the explanation is still pretty vague. It's poorly written, poorly explained.

5

Payne commented on Dec. 26, 2021, 3:20 a.m.

Really make sure you understand the explanation for the sample output before you begin writing any code. I wasted a lot of time because I misunderstood the question, don't make the same mistake.

-8

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

This problem can be solved without using float point.

This comment is hidden due to too much negative feedback. Show it anyway.

7

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!

13

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

51

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.

19

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!