Dada una array arr[] que consta de N enteros positivos y dos enteros X e Y , la tarea es verificar si es posible llegar a (X, Y) desde (0, 0) de manera que pasar a (X f , Y f ) de (X i , Y i ) solo se permite si la distancia euclidiana entre ellos está presente en la array arr[] . Si es posible, imprima Sí . De lo contrario, imprima No.
Nota: cada distancia presente en la array arr[] se puede usar como máximo una vez .
Ejemplos:
Entrada: arr[ ] = {2, 5}, X = 5, Y= 4
Salida: Sí
Explicación:
Los siguientes son los movimientos necesarios para llegar de (0, 0) a (5, 4):
- Muévete del punto (0, 0) al (2, 0). La distancia euclidiana es sqrt((2 – 0) 2 + (0 – 0)) = 2, que está presente en la array.
- Muévete del punto (2, 0) al (5, 4). La distancia euclidiana es sqrt((5 – 2) 2 + (4 – 0) 2 ) = 5, que está presente en la array.
Después del conjunto de movimientos anterior, se puede llegar al punto (5, 4). Por lo tanto, imprima Sí.
Entrada: arr[] = {4}, X = 3, Y= 4
Salida: No
Enfoque: El problema dado se puede resolver usando las siguientes observaciones al considerar la distancia euclidiana entre los puntos (0, 0) a (X, Y) como Z = sqrt(X*X + Y*Y) , entonces el problema se puede resolver. dividido en 3 casos:
- Si la suma del elemento de la array es menor que Z , es imposible llegar a (X, Y) mediante cualquier conjunto de movimientos.
- Si la suma del elemento de la array es igual a Z , es posible llegar a (X, Y) después de N movimientos.
- De lo contrario, para cada distancia, verifique las siguientes condiciones:
- Si para cualquier A[i] , A[i] > Z + (Todas las demás distancias excepto A[i]) , entonces nunca es posible llegar a (X, Y) porque la ruta será un polígono y para un N-polígono la suma de (N – 1) lados debe ser mayor que el otro lado para cada lado posible.
- De lo contrario, siempre es posible llegar al punto (X, Y) .
A partir de las observaciones anteriores considerando los tres casos, imprima el resultado en consecuencia.
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 the point (X, Y)
// is reachable from (0, 0) or not
int isPossibleToReach(int A[], int N, int X, int Y)
{
// Find the Euclidean Distance
double distance = sqrt(double(X * X + Y * Y));
// Calculate the maximum distance
double mx = 0;
for (int i = 0; i < N; i++) {
mx += double(A[i]);
}
// Case 1.
if (mx < distance) {
cout << "NO";
return 0;
}
// Case 2.
if ((mx - distance) < 0.000001) {
cout << "YES";
return 0;
}
// Otherwise, check for the polygon
// condition for each side
for (int i = 0; i < N; i++) {
if (distance + mx
< double(2) * double(A[i])) {
cout << "No";
return 0;
}
}
// Otherwise, print Yes
cout << "Yes";
return 0;
}
// Driver Code
int main()
{
int A[] = { 2, 5 };
int X = 5, Y = 4;
int N = sizeof(A) / sizeof(A[0]);
isPossibleToReach(A, N, X, Y);
return 0;
}
Java
// C# program for the above approach
import java.io.*;
class GFG{
// Function to check if the point (X, Y)
// is reachable from (0, 0) or not
static int isPossibleToReach(int []A, int N,
int X, int Y)
{
// Find the Euclidean Distance
double distance = Math.sqrt((X * X + Y * Y));
// Calculate the maximum distance
double mx = 0;
for(int i = 0; i < N; i++)
{
mx += (A[i]);
}
// Case 1.
if (mx < distance)
{
System.out.print("NO");
return 0;
}
// Case 2.
if ((mx - distance) < 0.000001)
{
System.out.print("YES");
return 0;
}
// Otherwise, check for the polygon
// condition for each side
for(int i = 0; i < N; i++)
{
if (distance + mx < 2 * A[i])
{
System.out.print("No");
return 0;
}
}
// Otherwise, print Yes
System.out.print("Yes");
return 0;
}
// Driver Code
public static void main (String[] args)
{
int []A = { 2, 5 };
int X = 5, Y = 4;
int N = A.length;
isPossibleToReach(A, N, X, Y);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python program for the above approach
import math
# Function to check if the po(X, Y)
# is reachable from (0, 0) or not
def isPossibleToReach(A, N, X, Y):
# Find the Euclidean Distance
distance = math.sqrt(X * X + Y * Y)
# Calculate the maximum distance
mx = 0
for i in range(N):
mx += A[i]
# Case 1.
if (mx < distance):
print("NO")
return 0
# Case 2.
if ((mx - distance) < 0.000001):
print("YES")
return 0
# Otherwise, check for the polygon
# condition for each side
for i in range(N):
if (distance + mx < (2) * (A[i])):
print("No")
return 0
# Otherwise, print Yes
print("Yes")
return 0
# Driver Code
A = [2, 5]
X = 5
Y = 4
N = len(A)
isPossibleToReach(A, N, X, Y)
# This code is contributed by shivani.
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the point (X, Y)
// is reachable from (0, 0) or not
static int isPossibleToReach(int []A, int N,
int X, int Y)
{
// Find the Euclidean Distance
double distance = Math.Sqrt((X * X + Y * Y));
// Calculate the maximum distance
double mx = 0;
for(int i = 0; i < N; i++)
{
mx += (A[i]);
}
// Case 1.
if (mx < distance)
{
Console.Write("NO");
return 0;
}
// Case 2.
if ((mx - distance) < 0.000001)
{
Console.Write("YES");
return 0;
}
// Otherwise, check for the polygon
// condition for each side
for(int i = 0; i < N; i++)
{
if (distance + mx < 2 * A[i])
{
Console.Write("No");
return 0;
}
}
// Otherwise, print Yes
Console.Write("Yes");
return 0;
}
// Driver Code
static public void Main ()
{
int []A = { 2, 5 };
int X = 5, Y = 4;
int N = A.Length;
isPossibleToReach(A, N, X, Y);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program for the above approach;
// Function to check if the point (X, Y)
// is reachable from (0, 0) or not
function isPossibleToReach(A, N, X, Y)
{
// Find the Euclidean Distance
let distance = Math.sqrt((X * X + Y * Y));
// Calculate the maximum distance
let mx = 0;
for (let i = 0; i < N; i++) {
mx += A[i];
}
// Case 1.
if (mx < distance) {
document.write("NO");
return 0;
}
// Case 2.
if ((mx - distance) < 0.000001) {
document.write("YES");
return 0;
}
// Otherwise, check for the polygon
// condition for each side
for (let i = 0; i < N; i++) {
if (distance + mx
< 2 * A[i]) {
document.write("No");
return 0;
}
}
// Otherwise, print Yes
document.write("Yes");
return 0;
}
// Driver Code
let A = [2, 5];
let X = 5, Y = 4;
let N = A.length;
isPossibleToReach(A, N, X, Y);
// This code is contributed by Potta Lokesh
</script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA