text: Queries on count of points lie inside a circle | C ++ program to find number of points lie inside or on the circumference of circle for Q queries . ; Computing the x ^ 2 + y ^ 2 for each given points and sorting them . ; Return count of points lie inside or on circumference of circle using binary search on p [ 0. . n - 1 ] ; Driven Program ; Compute distances of all points and keep the distances sorted so that query can work in O ( logn ) using Binary Search . ; Print number of points in a circle of radius 3. ; Print number of points in a circle of radius 32.
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void preprocess ( int p [ ] , int x [ ] , int y [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) p [ i ] = x [ i ] * x [ i ] + y [ i ] * y [ i ] ; sort ( p , p + n ) ; } int query ( int p [ ] , int n , int rad ) { int start = 0 , end = n - 1 ; while ( ( end - start ) > 1 ) { int mid = ( start + end ) / 2 ; double tp = sqrt ( p [ mid ] ) ; if ( tp > ( rad * 1.0 ) ) end = mid - 1 ; else start = mid ; } double tp1 = sqrt ( p [ start ] ) , tp2 = sqrt ( p [ end ] ) ; if ( tp1 > ( rad * 1.0 ) ) return 0 ; else if ( tp2 <= ( rad * 1.0 ) ) return end + 1 ; else return start + 1 ; } int main ( ) { int x [ ] = { 1 , 2 , 3 , -1 , 4 } ; int y [ ] = { 1 , 2 , 3 , -1 , 4 } ; int n = sizeof ( x ) / sizeof ( x [ 0 ] ) ; int p [ n ] ; preprocess ( p , x , y , n ) ; cout << query ( p , n , 3 ) << endl ; cout << query ( p , n , 32 ) << endl ; return 0 ; }