Choose jour language!

---

|

"KRUŽNE ZONE" - REŠENJE ZADATKA

Oblast: binarna pretraga, sortiranje niza

​#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;// data je sirina zona, a pamtimo poluprecnike koncentricnih krugova
        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 poz=0;
        bool nadjen=false;
        while(l<=d)
        {
            int s=(l+d)/2;
            double R2;
            R2=X[i]*X[i]+ Y[i]*Y[i];// kvadrat rastojanja
            double R=sqrt(R2);//rastojanje
            double rP=0;

            /*Odredjuje prethodni poluprecnik*/
            if(s-1<0)//ako je s pocetni index onda je manji krug prstena  poluprecnika jednakim nuli
            {
                rP=0;
            }
            else{
                rP=r[s-1];
            }
            /*da li pripada zoni*/
            if(R>rP && R<=r[s])
            {
                nadjen=true;
                poz=s;
                break;
            }
            else if(R<rP)
            {
                d=s-1;
            }
            else
            {
                l=s+1;
            }
        }
        if(nadjen)
        {
            cout<<poz<<endl;
        }
        else
        {
            cout<<"izvan"<<endl;
        }
    }

    return 0;
}