关于点数的查询位于圆内-yiteyi-C++库

鉴于 N 二维平面上点的坐标（x，y）和Q查询。每个查询都包含一个整数 R ，任务是计算半径为r且以原点为中心的圆的周长内或周长上的点数。 例如：

null

Input : n = 5Coordinates: 1 12 23 3-1 -14 4Query 1: 3Query 2: 32Output :35For first query radius = 3, number of points lieinside 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 areinside the circle.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

以原点（0，0）为圆心，半径为r，x的圆的方程 ^2. +y ^2. =r ^2. .和（x）点的条件 _1. Y _1. )躺在里面或周围，x _1. ^2. +y _1. ^2. <=r ^2. . A. 天真的方法 可以为每个查询遍历所有点并检查条件。这需要O（n*Q）时间复杂度。一 有效的方法 就是预计算x ^2. +y ^2. 对于每个点坐标，将其存储在数组p[]中。现在，对数组p[]进行排序。然后对数组进行二进制搜索，以查找条件p[i]<=r的最后一个索引 ^2. 对于每个查询。以下是该方法的实施情况：

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                       
                                                 elif                                     (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>                       

输出：

时间复杂性： O（n logn）用于预处理，O（Q logn）用于Q查询。本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章