Las consultas sobre el recuento de puntos se encuentran dentro de un círculo.

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *