Queries on count of points lie inside a circle | Python 3 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 ] ; Driver Code ; 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.
import math NEW_LINE def preprocess ( p , x , y , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT p [ i ] = x [ i ] * x [ i ] + y [ i ] * y [ i ] NEW_LINE DEDENT p . sort ( ) NEW_LINE DEDENT def query ( p , n , rad ) : NEW_LINE INDENT start = 0 NEW_LINE end = n - 1 NEW_LINE while ( ( end - start ) > 1 ) : NEW_LINE INDENT mid = ( start + end ) // 2 NEW_LINE tp = math . sqrt ( p [ mid ] ) NEW_LINE if ( tp > ( rad * 1.0 ) ) : NEW_LINE INDENT end = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT start = mid NEW_LINE DEDENT DEDENT tp1 = math . sqrt ( p [ start ] ) NEW_LINE tp2 = math . sqrt ( p [ end ] ) NEW_LINE if ( tp1 > ( rad * 1.0 ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif ( tp2 <= ( rad * 1.0 ) ) : NEW_LINE INDENT return end + 1 NEW_LINE DEDENT else : NEW_LINE INDENT return start + 1 NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x = [ 1 , 2 , 3 , - 1 , 4 ] NEW_LINE y = [ 1 , 2 , 3 , - 1 , 4 ] NEW_LINE n = len ( x ) NEW_LINE p = [ 0 ] * n NEW_LINE preprocess ( p , x , y , n ) NEW_LINE print ( query ( p , n , 3 ) ) NEW_LINE print ( query ( p , n , 32 ) ) NEW_LINE DEDENT