Radio antena

Neka su gradovi i radio tornjevi postavljeni na celobrojnoj \(x\) osi. Želimo da odredimo minimalnu dostižnost signala, tako da svi gradovi budu pokriveni radio signalom tornjeva.

Opis ulaza

Sa standardnog ulaza se unose celi brojevi \(n\) (broj gradova) i \(m\) (broj tornjeva) (\(0 < n, m < 10^5\)). Dalje se unosi \(n\) celih brojeva \(a_i\) (\(-10^5 < a_i < 10^5, 0 \leq i < n\)), koji predstavljaju pozicije gradova na \(x\) osi. Na kraju, unosi se \(m\) celih brojeva \(b_j\) (\(-10^5 < b_j < 10^5, 0 \leq j < m\)) koji predstavljaju pozicije tornjeva na \(x\) osi.

Opis izlaza

Na standardni izlaz ispisati dostižnost signala \(r\), tako da je ona minimalna moguća.

Primer 1

Ulaz

3 2
2 -2 4
-3 0

Izlaz

4

Primer 2

Ulaz

5 3
5 1 10 14 17
11 4 15

Izlaz

3

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

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

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

    vector<int> tower(m);
    for (int i = 0; i < m; i++) {
        cin >> tower[i];
    }

    sort(tower.begin(), tower.end());

    int radius = 0;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tower.begin(), tower.end(), town[i]);
       
        int dist = numeric_limits<int>::max();
        if (it != tower.begin()) {
            dist = min(dist, town[i] - *(it - 1));
        }
        if (it != tower.end()) {
            dist = min(dist, *it - town[i]);
        }

        radius = max(radius, dist);
    }

    cout << radius << endl;

    return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

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

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

    vector<int> tower(m);
    for (int i = 0; i < m; i++) {
        cin >> tower[i];
    }

    int radius = 0;
    for (int i = 0; i < n; i++) {
        int dist = numeric_limits<int>::max();
        for (int j = 0; j < m; j++) {
            dist = min(dist, abs(tower[j] - town[i]));
        }
        radius = max(radius, dist);
    }
    cout << radius << endl;

    return 0;
}