Dada la coordenada n (x, y) de los puntos en el plano 2D y las consultas Q. Cada consulta contiene un número entero r , la tarea es contar el número de puntos que se encuentran dentro o sobre la circunferencia del círculo que tiene radio r y está centrado en el origen.
Ejemplos:
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.
La ecuación para el círculo con centro en el origen (0, 0) con radio r, x 2 + y 2 = r 2 . Y condición para que un punto en (x 1 , y 1 ) esté dentro o sobre la circunferencia, x 1 2 + y 1 2 <= r 2 .
Un enfoque Naive puede ser para cada consulta, atravesar todos los puntos y verificar la condición. Esto toma una complejidad de tiempo O(n*Q).
Un enfoque eficiente es precalcular x 2 + y 2para cada coordenada de punto y almacenarlos en una array p[]. Ahora, ordene la array p[]. Luego aplique la búsqueda binaria en la array para encontrar el último índice con la condición p[i] <= r 2 para cada consulta.
A continuación se muestra la implementación de este enfoque:
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>
Producción:
3 5
Complejidad de tiempo: O(n log n) para preprocesamiento y O(Q Log n) para consultas Q.
Espacio Auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA