Check if given point lies in range of any of the given towers

0 0 5 minutes read

Given a 2D array arr[][] consisting of N rows of the form {X_i, Y_i, R_i} such that (X_i, Y_i) represents the position of a tower and R_i represents the network range of that tower. Given two integers X and Y, the task is to check if the point (X, Y) lies in the network range of the towers or not.

Examples:

Input: arr[][] = { {1, 1, 3}, {10, 10, 5}, {15, 15, 15} }, X = 5, Y = 5
Output: True
Explanation:
Distance of point(5, 5) from (arr[0][0], arr[0][1]) = 5.65685 and
the range of first tower is 3. Therefore, the point(X, Y) does not lie
in the network-range of the first tower.
Distance of point(5, 5) from (arr[1][0], arr[1][1]) = 7.07107 and
the range of second tower is 5. Therefore, the point(X, Y) does not lie
in the network-range of the second tower.
Distance of point(5, 5) from (arr[2][0], arr[2][1]) = 14.1421 and
the range of third tower is 15. Therefore, the point(X, Y) lies
in the network-range of the third tower.
Since, point (X, Y) lies in the range of the third tower.
Therefore, the required output is True.

Input: arr[][] = { {1, 1, 3}, {10, 10, 3}, {15, 15, 3} }, X = 5, Y = 5
Output: False

Approach: Follow the steps given below to solve the problem:

Traverse the array and for each row ( tower ) traversed,
- Check if the value of sqrt((arr[i][0] – x)² + (arr[i][1] – Y)²) is greater than arr[i][2] or not.
- If found to be true, then print True.
- Otherwise, print False.

Below is the implementation of the above approach.

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the point (X, Y)
// exists in the towers network-range or not
bool checkPointRange(int arr[][3], int X,
                     int Y, int N)
{
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
 
        // Stores distance of the
        // point (X, Y) from i-th tower
        double dist
            = sqrt((arr[i][0] - X) * (arr[i][0] - X)
                   + (arr[i][1] - Y) * (arr[i][1] - Y));
 
        // If dist lies within the
        // range of the i-th tower
        if (dist <= arr[i][2]) {
            return true;
        }
    }
 
    // If the point (X, Y) does not lie
    // in the range of any of the towers
    return false;
}
 
// Driver Code
int main()
{
 
    int arr[][3] = { { 1, 1, 3 }, 
                     { 10, 10, 3 }, 
                     { 15, 15, 15 } };
    int X = 5, Y = 5;
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // If point (X, Y) lies in the
    // range of any of the towers
    if (checkPointRange(arr, X, Y, N)) {
        cout << "True";
    }
    // Otherwise
    else {
        cout << "False";
    }
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
  
// Function to check if the point (X, Y)
// exists in the towers network-range or not
static boolean checkPointRange(int arr[][], int X,
                               int Y, int N)
{
     
    // Traverse the array arr[]
    for(int i = 0; i < N; i++) 
    {
         
        // Stores distance of the
        // point (X, Y) from i-th tower
        double dist = Math.sqrt((arr[i][0] - X) * 
                                (arr[i][0] - X) +
                                (arr[i][1] - Y) * 
                                (arr[i][1] - Y));
  
        // If dist lies within the
        // range of the i-th tower
        if (dist <= arr[i][2]) 
        {
            return true;
        }
    }
  
    // If the point (X, Y) does not lie
    // in the range of any of the towers
    return false;
}
  
// Driver Code
public static void main(String[] args)
{
    int arr[][] = { { 1, 1, 3 }, 
                    { 10, 10, 3 }, 
                    { 15, 15, 15 } };
    int X = 5, Y = 5;
  
    int N = arr.length;
  
    // If point (X, Y) lies in the
    // range of any of the towers
    if (checkPointRange(arr, X, Y, N))
    {
        System.out.print("True");
    }
     
    // Otherwise
    else
    {
        System.out.print("False");
    }
}
}
 
// This code is contributed by code_hunt

Python3

# Python3 program to implement
# the above approach
from math import sqrt
 
# Function to check if the point (X, Y)
# exists in the towers network-range or not
def checkPointRange(arr, X, Y, N):
     
    # Traverse the array arr[]
    for i in range(N):
         
        # Stores distance of the
        # point (X, Y) from i-th tower
        dist = sqrt((arr[i][0] - X) *
                    (arr[i][0] - X) +
                    (arr[i][1] - Y) *
                    (arr[i][1] - Y))
 
        # If dist lies within the
        # range of the i-th tower
        if (dist <= arr[i][2]):
            return True
 
    # If the point (X, Y) does not lie
    # in the range of any of the towers
    return False
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ [ 1, 1, 3 ], 
            [ 10, 10, 3 ],
            [ 15, 15, 15 ] ]
    X = 5
    Y = 5
 
    N =  len(arr)
 
    # If point (X, Y) lies in the
    # range of any of the towers
    if (checkPointRange(arr, X, Y, N)):
        print("True")
         
    # Otherwise
    else:
        print("False")
 
# This code is contributed by bgangwar59

C#

// C# program to implement
// the above approach  
using System;
   
class GFG{
   
// Function to check if the point (X, Y)
// exists in the towers network-range or not
static bool checkPointRange(int[,] arr, int X,
                            int Y, int N)
{
     
    // Traverse the array arr[]
    for(int i = 0; i < N; i++) 
    {
         
        // Stores distance of the
        // point (X, Y) from i-th tower
        double dist = Math.Sqrt((arr[i, 0] - X) * 
                                (arr[i, 0] - X) +
                                (arr[i, 1] - Y) * 
                                (arr[i, 1] - Y));
   
        // If dist lies within the
        // range of the i-th tower
        if (dist <= arr[i, 2]) 
        {
            return true;
        }
    }
   
    // If the point (X, Y) does not lie
    // in the range of any of the towers
    return false;
}
   
// Driver Code
public static void Main()
{
    int[,] arr = { { 1, 1, 3 }, 
                   { 10, 10, 3 }, 
                   { 15, 15, 15 } };
                     
    int X = 5, Y = 5;
   
    int N = arr.Length;
   
    // If point (X, Y) lies in the
    // range of any of the towers
    if (checkPointRange(arr, X, Y, N))
    {
        Console.Write("True");
    }
      
    // Otherwise
    else
    {
        Console.Write("False");
    }
}
}
   
// This code is contributed by susmitakundugoaldanga

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to check if the point (X, Y)
// exists in the towers network-range or not
function checkPointRange(arr, X, Y, N)
{
      
    // Traverse the array arr[]
    for(let i = 0; i < N; i++)
    {
          
        // Stores distance of the
        // point (X, Y) from i-th tower
        let dist = Math.sqrt((arr[i][0] - X) *
                                (arr[i][0] - X) +
                                (arr[i][1] - Y) *
                                (arr[i][1] - Y));
   
        // If dist lies within the
        // range of the i-th tower
        if (dist <= arr[i][2])
        {
            return true;
        }
    }
   
    // If the point (X, Y) does not lie
    // in the range of any of the towers
    return false;
}
 
// Driver Code
 
    let arr = [[ 1, 1, 3 ],
               [ 10, 10, 3 ],
              [ 15, 15, 15 ]];
    let X = 5, Y = 5;
   
    let N = arr.length;
   
    // If point (X, Y) lies in the
    // range of any of the towers
    if (checkPointRange(arr, X, Y, N))
    {
        document.write("True");
    }
      
    // Otherwise
    else
    {
        document.write("False");
    }
           
</script>

Output

True

Time Complexity: O(N * log(N)), in-built sqrt function has log(N) time complexity.
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!