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 1Output
0
0
1
2
izvanSolution (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;
}
R > 0. With lower_bound there is no such special case.Circular zone solution
Area: binary search, sorting array
#include <iostream>#include<math.h>
using namespace std;
#define DIMN 50000
#define DIMM 50000
int main()
{
int n,m;
double r[DIMN+1],sir=0,p=0;
double X[DIMM+1],Y[DIMM+1];
cin>>n;
for(int i=0; i<n; i++)
{
cin>>sir;
r[i]=p+sir;// the width of the zone is given, and we remember the semi-circles of concentric circles
p=r[i];
}
cin>>m;
for(int i=0; i<m; i++)
{
cin>>X[i]>>Y[i];
}
for(int i=0; i<m; i++)
{
int l=0;
int d=n-1;
int pos=0;
bool found=false;
while(l<=d)
{
int s=(l+d)/2;
double R2;
R2=X[i]*X[i]+ Y[i]*Y[i];// square distance
double R=sqrt(R2);//distance
double rP=0;
/*Specifies the previous radius*/
if(s-1<0)//If it is with the initial index, then the smaller ring of the semicircle is equal to zero
{
rP=0;
}
else{
rP=r[s-1];
}
/*whether it belongs to the zone*/
if(R>rP && R<=r[s])
{
found=true;
pos=s;
break;
}
else if(R<rP)
{
d=s-1;
}
else
{
l=s+1;
}
}
if(found)
{
cout<<pos<<endl;
}
else
{
cout<<"outside"<<endl;
}
}
return 0;
}
