Algoritmi → Binarna pretraga → Kružne zone – rešenje

Kružne zone – rešenje

Postavka

Meta se sastoji od n kružnih zona oko koordinatnog početka. Prva zona je krug, a svaka sledeća je kružni prsten oko prethodne. Zadate su širine zona redom od centra ka spolja. Za svaku od m tačaka (x, y) ispiši redni broj zone u kojoj se nalazi (zone se broje od 0) ili izvan ako je tačka van svih zona. Tačka na granici dve zone pripada unutrašnjoj zoni.

Ulaz: broj n, zatim n širina; broj m, zatim m parova koordinata (n, m ≤ 50 000).

Napomena: postavka je zapisana na osnovu postojećeg rešenja zadatka.

Primer

Ulaz

3
1 2 3
5
0 0
1 0
2 2
5 0
6 1

Izlaz

0
0
1
2
izvan

Rešenje (C++)

Ideja je objašnjena u uputstvu: iz širina se računaju granice zona, a za svaku tačku binarnom pretragom (lower_bound) nalazi prva granica koja nije manja od rastojanja tačke.

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

int main() {
    int n, m;
    cin >> n;
    vector<double> r(n);              // r[i] = poluprečnik spoljne granice zone i
    double p = 0;
    for (int i = 0; i < n; i++) {
        double sirina;
        cin >> sirina;
        p += sirina;                  // poluprečnik = zbir širina do te zone
        r[i] = p;
    }
    cin >> m;
    for (int k = 0; k < m; k++) {
        double x, y;
        cin >> x >> y;
        double R = sqrt(x * x + y * y);                        // rastojanje od centra
        int z = lower_bound(r.begin(), r.end(), R) - r.begin(); // prva granica >= R
        if (z == n) cout << "izvan" << endl;
        else cout << z << endl;
    }
    return 0;
}
Ispravka u odnosu na staru verziju: ranije rešenje je tačku u samom centru (R = 0) prijavljivalo kao „izvan“, jer je uslov za zonu 0 bio R > 0. Sa lower_bound takav poseban slučaj ne postoji.