Challenging Time

Its time for yet another challenge, and this time it has been prepared by none other than Monk himself for Super-Hardworking Programmers like you. So, this is how it goes:\nGiven N points located on the co-ordinate plane, where the ith point is located at co-ordinate (xi, yi), you need to answer q queries.\nIn the ith query, you shall be given an integer ri, and considering you draw a circle centered at the origin (0,0)with radius ri, you need to report the number of points lying inside or on the circumference of this circle.\nFor each query, you need to print the answer on a new line.\nInput Format :\nThe first line contains a single integer N denoting the number of points lying on the co-ordinate plane. Each of the next N lines contains 2 space separated integers xi and yi, denoting the x and y co-ordintaes of the ithpoint.\nThe next line contains a single integer q, denoting the number of queries. Each of the next q lines contains a single integer, where the integer on the ith line denotes the parameters of the ith query ri.\nOutput Format :\nFor each query, print the answer on a new line\n.

“TESTCASE_1”: “5\n1 1\n2 2\n3 3\n-1 -1\n4 4\n2\n3\n32\n###—###SEPERATOR—###—\n3\n5”, “TESTCASE_2”: “4\n3 3\n-2 -2\n4 4\n11 11\n2\n6\n45\n###—###SEPERATOR—###—\n3\n4”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

#include <stdio.h>
#include <stdlib.h>
 
int cmpfunc (const void * a, const void * b)
{
    if( *(double*)a > *(double*)b )
        return 1;
    else if( *(double*)a < *(double*)b )
        return -1;
    else
        return 0;
}
 
long long search(double *A, long long size, double element) {
    long long start=0;
    long long end = size-1;
    long long mid;
    long long first=-1;
    long long last =-1;
    double el = element*element;
    while(start<=end) {
        mid = (start+end)/2;
        if(el==A[mid]) {
            first = mid;
            end = mid-1;
        }
        else if(el<A[mid])
            end = mid-1;
        else if (el >A[mid])
            start = mid+1;
    }
    
    if(first == -1) {
        if( A[mid]<el)
            return mid+1;
        else
            return mid;    
    }
    else {
        start = first+1;
        last = first;
        end = size-1;
        while(start<=end) {
            mid = (start+end)/2;
            if(el==A[mid]) {
                last = mid;
                start = mid+1;
            }
            else if(el<A[mid])
                end = mid-1;
            else if (el >A[mid])
                start = mid+1;
        }
        
        return last+1;
    }
}
 
int main()
{
    long long N;
    double coord[100000];
    double x,y;
    long long q;
    double r;
    long long i;
    scanf("%lld",&N);
    for(i=0;i<N;i++) {
        scanf("%lf %lf",&x,&y);
        coord[i]= x*x + y*y;
    }
    
    qsort(coord,N,sizeof(double),cmpfunc);
    
    scanf("%lld",&q);
    for(i=0;i<q;i++) {
        scanf("%lf",&r);
        printf("%lld\n",search(coord,N,r));
    }
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro