Circular zones – solution

The task

A target consists of n circular zones around the origin. The first zone is a circle, and each next one is a ring around the previous one. The widths of the zones are given in order from the center outwards. For each of m points (x, y) print the number of the zone it is in (zones are numbered from 0) or izvan (outside) if the point is outside all zones. A point on the border of two zones belongs to the inner zone.

Input: the number n, then n widths; the number m, then m pairs of coordinates (n, m ≤ 50,000).

Note: the task text was written down from the existing solution of the task.

Example

Input

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

Output

0
0
1
2
izvan

Solution (C++)

The idea is explained in the hints: the zone borders are computed from the widths, and for each point binary search (lower_bound) finds the first border that is not smaller than the distance of the point.

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

int main() {
    int n, m;
    cin >> n;
    vector<double> r(n);              // r[i] = the radius of the outer border of zone i
    double p = 0;
    for (int i = 0; i < n; i++) {
        double sirina;
        cin >> sirina;
        p += sirina;                  // radius = the sum of the widths up to that 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);                        // distance from the center
        int z = lower_bound(r.begin(), r.end(), R) - r.begin(); // the first border >= R
        if (z == n) cout << "izvan" << endl;
        else cout << z << endl;
    }
    return 0;
}
Fix compared with the old version: the earlier solution reported a point exactly at the center (R = 0) as “outside”, because the condition for zone 0 was R > 0. With lower_bound there is no such special case.