Queries on count of points lie inside a circle
Given n coordinate (x, y) of points on 2D plane and Q queries. Each query contains an integer r, the task is to count the number of points lying inside or on the circumference of the circle having radius r and centered at the origin.
Examples :
Input : n = 5 Coordinates: 1 1 2 2 3 3 -1 -1 4 4 Query 1: 3 Query 2: 32 Output : 3 5 For first query radius = 3, number of points lie inside or on the circumference are (1, 1), (-1, -1), (2, 2). There are only 3 points lie inside or on the circumference of the circle. For second query radius = 32, all five points are inside the circle.
The equation for the circle centered at origin (0, 0) with radius r, x2 + y2 = r2. And condition for a point at (x1, y1) to lie inside or on the circumference, x12 + y12 <= r2.
A Naive approach can be for each query, traverse through all points and check the condition. This take O(n*Q) time complexity.
An Efficient approach is to precompute x2 + y2 for each point coordinate and store them in an array p[]. Now, sort the array p[]. Then apply binary search on the array to find last index with condition p[i] <= r2 for each query.
Below is the implementation of this approach:
C++
// C++ program to find number of points lie inside or // on the circumference of circle for Q queries. #include <bits/stdc++.h> using namespace std; // Computing the x^2 + y^2 for each given points // and sorting them. 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); } // Return count of points lie inside or on circumference // of circle using binary search on p[0..n-1] 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; } // Driven Program int main() { int x[] = { 1, 2, 3, -1, 4 }; int y[] = { 1, 2, 3, -1, 4 }; int n = sizeof (x) / sizeof (x[0]); // Compute distances of all points and keep // the distances sorted so that query can // work in O(logn) using Binary Search. int p[n]; preprocess(p, x, y, n); // Print number of points in a circle of radius 3. cout << query(p, n, 3) << endl; // Print number of points in a circle of radius 32. cout << query(p, n, 32) << endl; return 0; } |
Java
// JAVA Code for Queries on count of // points lie inside a circle import java.util.*; class GFG { // Computing the x^2 + y^2 for each given points // and sorting them. public static 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]; Arrays.sort(p); } // Return count of points lie inside or on // circumference of circle using binary // search on p[0..n-1] public static 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 = Math.sqrt(p[mid]); if (tp > (rad * 1.0 )) end = mid - 1 ; else start = mid; } double tp1 = Math.sqrt(p[start]); double tp2 = Math.sqrt(p[end]); if (tp1 > (rad * 1.0 )) return 0 ; else if (tp2 <= (rad * 1.0 )) return end + 1 ; else return start + 1 ; } /* Driver program to test above function */ public static void main(String[] args) { int x[] = { 1 , 2 , 3 , - 1 , 4 }; int y[] = { 1 , 2 , 3 , - 1 , 4 }; int n = x.length; // Compute distances of all points and keep // the distances sorted so that query can // work in O(logn) using Binary Search. int p[] = new int [n]; preprocess(p, x, y, n); // Print number of points in a circle of // radius 3. System.out.println(query(p, n, 3 )); // Print number of points in a circle of // radius 32. System.out.println(query(p, n, 32 )); } } // This code is contributed by Arnav Kr. Mandal. |
Python 3
# Python 3 program to find number of # points lie inside or on the circumference # of circle for Q queries. import math # Computing the x^2 + y^2 for each # given points and sorting them. def preprocess(p, x, y, n): for i in range (n): p[i] = x[i] * x[i] + y[i] * y[i] p.sort() # Return count of points lie inside # or on circumference of circle using # binary search on p[0..n-1] def query(p, n, rad): start = 0 end = n - 1 while ((end - start) > 1 ): mid = (start + end) / / 2 tp = math.sqrt(p[mid]) if (tp > (rad * 1.0 )): end = mid - 1 else : start = mid tp1 = math.sqrt(p[start]) tp2 = math.sqrt(p[end]) if (tp1 > (rad * 1.0 )): return 0 else if (tp2 < = (rad * 1.0 )): return end + 1 else : return start + 1 # Driver Code if __name__ = = "__main__" : x = [ 1 , 2 , 3 , - 1 , 4 ] y = [ 1 , 2 , 3 , - 1 , 4 ] n = len (x) # Compute distances of all points and keep # the distances sorted so that query can # work in O(logn) using Binary Search. p = [ 0 ] * n preprocess(p, x, y, n) # Print number of points in a # circle of radius 3. print (query(p, n, 3 )) # Print number of points in a # circle of radius 32. print (query(p, n, 32 )) # This code is contributed by ita_c |
C#
// C# Code for Queries on count of // points lie inside a circle using System; class GFG { // Computing the x^2 + y^2 for each // given points and sorting them. public static 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]; Array.Sort(p); } // Return count of points lie inside or on // circumference of circle using binary // search on p[0..n-1] public static 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 = Math.Sqrt(p[mid]); if (tp > (rad * 1.0)) end = mid - 1; else start = mid; } double tp1 = Math.Sqrt(p[start]); double tp2 = Math.Sqrt(p[end]); if (tp1 > (rad * 1.0)) return 0; else if (tp2 <= (rad * 1.0)) return end + 1; else return start + 1; } /* Driver program to test above function */ public static void Main() { int [] x = { 1, 2, 3, -1, 4 }; int [] y = { 1, 2, 3, -1, 4 }; int n = x.Length; // Compute distances of all points and keep // the distances sorted so that query can // work in O(logn) using Binary Search. int [] p = new int [n]; preprocess(p, x, y, n); // Print number of points in a circle of // radius 3. Console.WriteLine(query(p, n, 3)); // Print number of points in a circle of // radius 32. Console.WriteLine(query(p, n, 32)); } } // This code is contributed by vt_m. |
Javascript
<script> // Javascript Code for Queries on count of // points lie inside a circle // Computing the x^2 + y^2 for each given points // and sorting them. function preprocess(p,x,y,n) { for (let i = 0; i < n; i++) p[i] = x[i] * x[i] + y[i] * y[i]; p.sort( function (a,b){ return a-b;}); } // Return count of points lie inside or on // circumference of circle using binary // search on p[0..n-1] function query(p,n,rad) { let start = 0, end = n - 1; while ((end - start) > 1) { let mid = Math.floor((start + end) / 2); let tp = Math.sqrt(p[mid]); if (tp > (rad * 1.0)) end = mid - 1; else start = mid; } let tp1 = Math.sqrt(p[start]); let tp2 = Math.sqrt(p[end]); if (tp1 > (rad * 1.0)) return 0; else if (tp2 <= (rad * 1.0)) return end + 1; else return start + 1; } /* Driver program to test above function */ let x=[1, 2, 3, -1, 4 ]; let y=[1, 2, 3, -1, 4]; let n = x.length; // Compute distances of all points and keep // the distances sorted so that query can // work in O(logn) using Binary Search. let p= new Array(n); for (let i=0;i<n;i++) { p[i]=0; } preprocess(p, x, y, n); // Print number of points in a circle of // radius 3. document.write(query(p, n, 3)+ "<br>" ); // Print number of points in a circle of // radius 32. document.write(query(p, n, 32)+ "<br>" ); // This code is contributed by rag2127 </script> |
Output:
3 5
Time Complexity: O(n log n) for preprocessing and O(Q Log n) for Q queries.
Auxiliary Space: O(n) it is using extra space for array p