vanya-and-lanterns

Vanya and Lanterns

You are given a line of length \(l\) and \(n\) points on it at positions \(a_1, a_2, \dots, a_n\). Each point can “cover” a distance \(d\) to the left and \(d\) to the right. Find the smallest \(d\) so that every point on the line from \(0\) to \(l\) is covered by at least one of these points.

Note

To print a double variable named x in a normal decimal format, you can use cout << fixed << x;

Solution

First, we sort the points from left to right so that their order in the array matches their positions on the line.

To make sure the line is fully covered, each point must cover at least half the distance to its neighbor, which is \((a_{i+1} - a_i)/2\) for each \(i\).

The first point \(a_1\) must also cover the distance from the start of the line (0) to itself, \(a_1 - 0\), and the last point \(a_n\) must cover the distance from itself to the end of the line, \(l - a_n\).

The smallest \(d\) that ensures the whole line is covered is the largest of all these distances.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, l;
    cin >> n >> l;

    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a, a + n);

    double d = max(a[0] - 0, l - a[n - 1]);

    for (int i = 0; i < n - 1; i++) {
        d = max(d, (a[i + 1] - a[i]) / 2.0);
    }

    cout << fixed << d << "\n";
}