Dados dos arreglos A[] y B[] que consisten en coordenadas X e Y de N puntos distintos en un plano, y un entero positivo K , la tarea es verificar si existe algún punto P en el plano tal que la distancia de Manhattan entre el punto y todos los puntos dados es como máximo K . Si existe tal punto P , imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: A[] = {1, 0, 2, 1, 1}, B[] = {1, 1, 1, 0, 2}, K = 1
Salida: Sí
Explicación:
Considere un punto P(1, 1 ), entonces la distancia de Manhattan entre P y todos los puntos dados son:
- La distancia entre P y (A[0], B[0]) es |1 – 1| + |1 – 1| = 0.
- La distancia entre P y (A[1], B[1]) es |1 – 0| + |1 – 1| = 1.
- La distancia entre P y (A[2], B[2]) es |1 – 2| + |1 – 1| = 1.
- La distancia entre P y (A[3], B[3]) es |1 – 1| + |1 – 0| = 1.
- La distancia entre P y (A[4], B[4]) es |1 – 1| + |1 – 2| = 1.
La distancia entre todos los puntos dados y P es como máximo K(= 1). Por lo tanto, imprima «Sí».
Entrada: A[] = {0, 3, 1}, B[] = {0, 3, 1}, K = 2
Salida: No
Enfoque: El problema dado se puede resolver encontrando la distancia de Manhattan entre cada par de N puntos dados . Después de comprobar todos los pares de puntos, si el recuento de la distancia entre pares de puntos es como máximo K, imprima «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to check if there
// exists any point with at most
// K distance from N given points
string find(int a[], int b[], int N, int K)
{
// Traverse the given N points
for(int i = 0; i < N; i++)
{
// Stores the count of pairs
// of coordinates having
// Manhattan distance <= K
int count = 0;
for(int j = 0; j < N; j++)
{
// For the same coordinate
if (i == j)
{
continue;
}
// Calculate Manhattan distance
long long int dis = abs(a[i] - a[j]) +
abs(b[i] - b[j]);
// If Manhattan distance <= K
if (dis <= K)
{
count++;
}
// If all coordinates
// can meet
if (count == N - 1)
{
return "Yes";
}
}
}
// If all coordinates can't meet
return "No";
}
// Driver Code
int main()
{
int N = 5;
int A[] = { 1, 0, 2, 1, 1 };
int B[] = { 1, 1, 1, 0, 2 };
int K = 1;
cout << find(A, B, N, K) << endl;
}
// This code is contributed by bgangwar59
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to check if there
// exists any point with at most
// K distance from N given points
public static String find(
int[] a, int[] b, int N, int K)
{
// Traverse the given N points
for (int i = 0; i < N; i++) {
// Stores the count of pairs
// of coordinates having
// Manhattan distance <= K
int count = 0;
for (int j = 0; j < N; j++) {
// For the same coordinate
if (i == j) {
continue;
}
// Calculate Manhattan distance
long dis = Math.abs(a[i] - a[j])
+ Math.abs(b[i] - b[j]);
// If Manhattan distance <= K
if (dis <= K) {
count++;
}
// If all coordinates
// can meet
if (count == N - 1) {
return "Yes";
}
}
}
// If all coordinates can't meet
return "No";
}
// Driver Code
public static void main(String[] args)
{
int N = 5;
int[] A = { 1, 0, 2, 1, 1 };
int[] B = { 1, 1, 1, 0, 2 };
int K = 1;
System.out.println(
find(A, B, N, K));
}
}
Python3
# Python3 program for the above approach # Function to check if there # exists any point with at most # K distance from N given points def find(a, b, N, K): # Traverse the given n points for i in range(N): # Stores the count of pairs # of coordinates having # Manhattan distance <= K count = 0 for j in range(N): # For the same coordinate if (i == j): continue # Calculate Manhattan distance dis = abs(a[i] - a[j]) + abs(b[i] - b[j]) # If Manhattan distance <= K if (dis <= K): count = count + 1 # If all coordinates # can meet if (count == N - 1): return "Yes" # If all coordinates can't meet return "No" # Driver code N = 5 A = [ 1, 0, 2, 1, 1 ] B = [ 1, 1, 1, 0, 2 ] K = 1 print(find(A, B, N, K)) # This code is contributed by abhinavjain194
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if there
// exists any point with at most
// K distance from N given points
public static String find(int[] a, int[] b,
int N, int K)
{
// Traverse the given N points
for(int i = 0; i < N; i++)
{
// Stores the count of pairs
// of coordinates having
// Manhattan distance <= K
int count = 0;
for(int j = 0; j < N; j++)
{
// For the same coordinate
if (i == j)
{
continue;
}
// Calculate Manhattan distance
long dis = Math.Abs(a[i] - a[j]) +
Math.Abs(b[i] - b[j]);
// If Manhattan distance <= K
if (dis <= K)
{
count++;
}
// If all coordinates
// can meet
if (count == N - 1)
{
return "Yes";
}
}
}
// If all coordinates can't meet
return "No";
}
// Driver Code
public static void Main(string[] args)
{
int N = 5;
int[] A = { 1, 0, 2, 1, 1 };
int[] B = { 1, 1, 1, 0, 2 };
int K = 1;
Console.WriteLine(find(A, B, N, K));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for
// the above approach
// Function to check if there
// exists any point with at most
// K distance from N given points
function find(a, b, N, K) {
// Traverse the given N points
for (let i = 0; i < N; i++) {
// Stores the count of pairs
// of coordinates having
// Manhattan distance <= K
let count = 0;
for (let j = 0; j < N; j++) {
// For the same coordinate
if (i == j) {
continue;
}
// Calculate Manhattan distance
let dis = Math.abs(a[i] - a[j]) +
Math.abs(b[i] - b[j]);
// If Manhattan distance <= K
if (dis <= K) {
count++;
}
// If all coordinates
// can meet
if (count == N - 1) {
return "Yes";
}
}
}
// If all coordinates can't meet
return "No";
}
// Driver Code
let N = 5;
let A = [ 1, 0, 2, 1, 1 ];
let B = [ 1, 1, 1, 0, 2 ];
let K = 1;
document.write(find(A, B, N, K));
// This code is contributed by Hritik
</script>
Yes
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aditya7409 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA