Given a 2D array arr[][] consisting of N rows of the form {Xi, Yi, Ri} such that (Xi, Yi) represents the position of a tower and Ri 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)2 + (arr[i][1] – Y)2) 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 notbool 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 Codeint 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 approachimport java.util.*;class GFG{ // Function to check if the point (X, Y)// exists in the towers network-range or notstatic 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 Codepublic 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 approachfrom math import sqrt# Function to check if the point (X, Y)# exists in the towers network-range or notdef 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 Codeif __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 notstatic 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 Codepublic 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 notfunction 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> |
True
Time Complexity: O(N * log(N)), in-built sqrt function has log(N) time complexity.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
