CCC 2018 S1: Voronoi Villages

The boundaries of a neighbourhood are defined by the two adjacent villages.

1. Sort the villages,.

2. Compute the midpoint of each adjacent pair of villages to obtain the neighbourhood boundaries.

3. iterate over all the boundaries and compute the size of each neighbourhood, and output size of the smallest one.

#include <iostream>

#include <limits>

#include <algorithm>

#include <iomanip>

using namespace std;

#define MAXN 105

#define D_INF numeric_limits<double>::infinity()

int N, V[MAXN];

double ans = D_INF;

int main() {

    cin >> N;

    for(int i = 0; i < N; i++)

    	cin >> V[i];

    sort(V, V + N);

    for(int i = 1; i < N-1; i++){

    	double cur = (V[i + 1] - V[i - 1]) / 2.0;

    	if(ans > cur)

    		ans = cur;

    }

    cout << setprecision(1) << fixed << ans << endl;

    return 0;

}