top of page

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;

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,


bottom of page