Рубрики

Запросы на подсчет очков лежат внутри круга

Даны n координат (x, y) точек на 2D плоскости и Q запросов. Каждый запрос содержит целое число r , задача состоит в том, чтобы подсчитать количество точек, лежащих внутри или на окружности круга, имеющего радиус r и центрированного в начале координат.

Примеры :

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. 

Уравнение для окружности с центром в начале координат (0, 0) с радиусом r, x 2 + y 2 = r 2 . И условие для точки в (x 1 , y 1 ) лежать внутри или на окружности, x 1 2 + y 1 2 <= r 2 .

Наивный подход может быть для каждого запроса, пройти через все точки и проверить условие. Это займет O (n * Q) сложность времени.

Эффективный подход состоит в том, чтобы предварительно вычислить x 2 + y 2 для каждой координаты точки и сохранить их в массиве p []. Теперь сортируем массив p []. Затем примените двоичный поиск по массиву, чтобы найти последний индекс с условием p [i] <= r 2 для каждого запроса.

Ниже приведена реализация этого подхода:

C ++

// C ++ программа для определения количества точек, лежащих внутри или
// об окружности круга для Q запросов.
#include <bits/stdc++.h>

using namespace std;

  
// Вычисление x ^ 2 + y ^ 2 для каждой заданной точки
// и сортируем их.

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);

}

  
// Возвращаем количество точек лежащих внутри или по окружности
// круга, использующего бинарный поиск по 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;

}

  
// Управляемая программа

int main()

{

    int x[] = { 1, 2, 3, -1, 4 };

    int y[] = { 1, 2, 3, -1, 4 };

    int n = sizeof(x) / sizeof(x[0]);

  

    // Вычисляем расстояния всех точек и сохраняем

    // расстояния отсортированы так, что запрос может

    // работа в O (logn) с использованием бинарного поиска.

    int p[n];

    preprocess(p, x, y, n);

  

    // Вывести количество точек в окружности радиуса 3.

    cout << query(p, n, 3) << endl;

  

    // Вывести количество точек в окружности радиусом 32.

    cout << query(p, n, 32) << endl;

    return 0;

}

Джава

// JAVA-код для запросов на счет
// точки лежат внутри круга

import java.util.*;

  

class GFG {

  

    // Вычисление x ^ 2 + y ^ 2 для каждой заданной точки

    // и сортируем их.

    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);

    }

  

    // Возвращаем количество точек лежащих внутри или на

    // окружность круга с использованием двоичного

    // поиск по 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;

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String[] args)

    {

        int x[] = { 1, 2, 3, -1, 4 };

        int y[] = { 1, 2, 3, -1, 4 };

        int n = x.length;

  

        // Вычисляем расстояния всех точек и сохраняем

        // расстояния отсортированы так, что запрос может

        // работа в O (logn) с использованием бинарного поиска.

        int p[] = new int[n];

        preprocess(p, x, y, n);

  

        // Вывести количество точек по кругу

        // радиус 3.

        System.out.println(query(p, n, 3));

  

        // Вывести количество точек по кругу

        // радиус 32.

        System.out.println(query(p, n, 32));

    }

}
// Этот код предоставлен Арнавом Кр. Мандал.

Python 3

# Python 3 программа для поиска номера
# точки лежат внутри или на окружности
# круга для Q запросов.

import math

  
# Вычисление x ^ 2 + y ^ 2 для каждого
# заданные баллы и сортировка их.

def preprocess(p, x, y, n):

    for i in range(n):

        p[i] = x[i] * x[i] + y[i] * y[i]

  

    p.sort()

  
# Возвращаемое количество очков лежит внутри
# или по окружности, используя
# бинарный поиск на 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

  
Код водителя

if __name__ == "__main__":

      

    x = [ 1, 2, 3, -1, 4 ]

    y = [ 1, 2, 3, -1, 4 ]

    n = len(x)

  

    # Вычислить расстояния всех точек и сохранить

    # расстояния, отсортированные так, чтобы запрос мог

    # работать в O (logn) с помощью бинарного поиска.

    p = [0] * n

    preprocess(p, x, y, n)

  

    # Вывести количество точек в

    # круг радиуса 3.

    print(query(p, n, 3))

  

    # Вывести количество точек в

    # круг радиуса 32.

    print(query(p, n, 32))

  
# Этот код предоставлен ita_c

C #

// C # код для запросов на счет
// точки лежат внутри круга

using System;

  

class GFG {

  

    // Вычисление x ^ 2 + y ^ 2 для каждого

    // заданные баллы и сортировка их.

    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);

    }

  

    // Возвращаем количество точек лежащих внутри или на

    // окружность круга с использованием двоичного

    // поиск по 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;

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void Main()

    {

        int[] x = { 1, 2, 3, -1, 4 };

        int[] y = { 1, 2, 3, -1, 4 };

        int n = x.Length;

  

        // Вычисляем расстояния всех точек и сохраняем

        // расстояния отсортированы так, что запрос может

        // работа в O (logn) с использованием бинарного поиска.

        int[] p = new int[n];

        preprocess(p, x, y, n);

  

        // Вывести количество точек по кругу

        // радиус 3.

        Console.WriteLine(query(p, n, 3));

  

        // Вывести количество точек по кругу

        // радиус 32.

        Console.WriteLine(query(p, n, 32));

    }

}

  
// Этот код предоставлен vt_m.


Выход:

3
5

Сложность времени: O (n log n) для предварительной обработки и O (Q Log n) для Q запросов.

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Запросы на подсчет очков лежат внутри круга

0.00 (0%) 0 votes