Choose jour language!

---

|

​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;
}