Dadas N líneas y un punto de partida y un punto de destino en un espacio bidimensional. Estas N líneas dividen el espacio en algunos bloques. Necesitamos imprimir el número mínimo de saltos para llegar al punto de destino desde el punto de partida. Podemos saltar de un bloque a otro bloque solo si comparten un lado. Ejemplos:
Input : Lines = [x = 0, y = 0, x + y – 2 = 0]
Start point = [1, 1],
Dest point = [-2, -1]
Output : 2
We need to jump 2 times (B4 -> B3 then B3 -> B5
or B4 -> B6 then B6 -> B5) to reach destination
point from starting point shown in below diagram.
Each block i is given an id Bi in the diagram.
Podemos resolver este problema usando una propiedad de líneas y puntos que se establece como, si ponemos dos puntos en la ecuación de la línea, entonces tendrán el mismo signo, es decir, positivo-positivo o negativo-negativo del valor evaluado si ambos puntos se encuentran en el mismo lado. de línea, en caso de diferente signo, es decir, positivo-negativo, estarán en diferentes lados de la línea. Ahora podemos usar la propiedad anterior para resolver este problema. Para cada línea, verificaremos si el punto de inicio y el de destino se encuentran en el mismo lado o no. Si se encuentran en el lado diferente de una línea, entonces esa línea debe saltarse para acercarse. Como en el diagrama anterior, el punto de inicio y el punto de destino están en el mismo lado de la línea x + y – 2 = 0, por lo que no es necesario saltar esa línea, se deben saltar dos líneas restantes porque ambos puntos se encuentran en el lado opuesto. Finalmente, comprobaremos el signo de evaluación de puntos con respecto a cada línea y aumentaremos nuestra cuenta de saltos siempre que encontremos signos opuestos. La complejidad temporal total de este problema será lineal.
C++
// C++ program to find minimum jumps to reach
// a given destination from a given source
#include <bits/stdc++.h>
using namespace std;
// To represent point in 2D space
struct point
{
int x, y;
point(int x, int y) : x(x), y(y)
{}
};
// To represent line of (ax + by + c)format
struct line
{
int a, b, c;
line(int a, int b, int c) : a(a), b(b), c(c)
{}
line()
{}
};
// Returns 1 if evaluation is greater > 0,
// else returns -1
int evalPointOnLine(point p, line curLine)
{
int eval = curLine.a* p.x +
curLine.b * p.y +
curLine.c;
if (eval > 0)
return 1;
return -1;
}
// Returns minimum jumps to reach
// dest point from start point
int minJumpToReachDestination(point start,
point dest, line lines[], int N)
{
int jumps = 0;
for (int i = 0; i < N; i++)
{
// get sign of evaluation from point
// co-ordinate and line equation
int signStart = evalPointOnLine(start, lines[i]);
int signDest = evalPointOnLine(dest, lines[i]);
// if both evaluation are of opposite sign,
// increase jump by 1
if (signStart * signDest < 0)
jumps++;
}
return jumps;
}
// Driver code to test above methods
int main()
{
point start(1, 1);
point dest(-2, -1);
line lines[3];
lines[0] = line(1, 0, 0);
lines[1] = line(0, 1, 0);
lines[2] = line(1, 1, -2);
cout << minJumpToReachDestination(start, dest, lines, 3);
return 0;
}
Java
// Java program to find minimum jumps to reach
// a given destination from a given source
class GFG
{
// To represent point in 2D space
static class point
{
int x, y;
public point(int x, int y)
{
super();
this.x = x;
this.y = y;
}
};
// To represent line of (ax + by + c)format
static class line
{
public line(int a, int b, int c)
{
this.a = a;
this.b = b;
this.c = c;
}
int a, b, c;
line()
{}
};
// Returns 1 if evaluation is greater > 0,
// else returns -1
static int evalPointOnLine(point p, line curLine)
{
int eval = curLine.a* p.x +
curLine.b * p.y +
curLine.c;
if (eval > 0)
return 1;
return -1;
}
// Returns minimum jumps to reach
// dest point from start point
static int minJumpToReachDestination(point start,
point dest, line lines[], int N)
{
int jumps = 0;
for (int i = 0; i < N; i++)
{
// get sign of evaluation from point
// co-ordinate and line equation
int signStart = evalPointOnLine(start, lines[i]);
int signDest = evalPointOnLine(dest, lines[i]);
// if both evaluation are of opposite sign,
// increase jump by 1
if (signStart * signDest < 0)
jumps++;
}
return jumps;
}
// Driver code
public static void main(String[] args)
{
point start = new point(1, 1);
point dest = new point(-2, -1);
line []lines = new line[3];
lines[0] = new line(1, 0, 0);
lines[1] = new line(0, 1, 0);
lines[2] = new line(1, 1, -2);
System.out.print(minJumpToReachDestination(start, dest, lines, 3));
}
}
// This code is contributed by Rajput-Ji
C#
// C# program to find minimum jumps to reach
// a given destination from a given source
using System;
class GFG
{
// To represent point in 2D space
class point
{
public int x, y;
public point(int x, int y)
{
this.x = x;
this.y = y;
}
};
// To represent line of (ax + by + c)format
class line
{
public int a, b, c;
line()
{}
public line(int a, int b, int c)
{
this.a = a;
this.b = b;
this.c = c;
}
};
// Returns 1 if evaluation is greater > 0,
// else returns -1
static int evalPointOnLine(point p, line curLine)
{
int eval = curLine.a* p.x +
curLine.b * p.y +
curLine.c;
if (eval > 0)
return 1;
return -1;
}
// Returns minimum jumps to reach
// dest point from start point
static int minJumpToReachDestination(point start,
point dest, line []lines, int N)
{
int jumps = 0;
for (int i = 0; i < N; i++)
{
// get sign of evaluation from point
// co-ordinate and line equation
int signStart = evalPointOnLine(start, lines[i]);
int signDest = evalPointOnLine(dest, lines[i]);
// if both evaluation are of opposite sign,
// increase jump by 1
if (signStart * signDest < 0)
jumps++;
}
return jumps;
}
// Driver code
public static void Main(String[] args)
{
point start = new point(1, 1);
point dest = new point(-2, -1);
line []lines = new line[3];
lines[0] = new line(1, 0, 0);
lines[1] = new line(0, 1, 0);
lines[2] = new line(1, 1, -2);
Console.Write(minJumpToReachDestination(start, dest, lines, 3));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program to find minimum jumps to reach # a given destination from a given source # To represent point in 2D space class point: def __init__(self, x, y): self.x = x self.y = y # To represent line of (ax + by + c)format class line: def __init__(self, a, b, c): self.a = a self.b = b self.c = c # Returns 1 if evaluation is greater > 0, # else returns -1 def evalPointOnLine(p, curLine): eval = curLine.a * p.x + curLine.b * p.y + curLine.c if (eval > 0): return 1 return -1 # Returns minimum jumps to reach # dest point from start point def minJumpToReachDestination(start, dest, lines, N): jumps = 0 for i in range(N): # get sign of evaluation from point # co-ordinate and line equation signStart = evalPointOnLine(start, lines[i]) signDest = evalPointOnLine(dest, lines[i]) # if both evaluation are of opposite sign, # increase jump by 1 if (signStart * signDest < 0): jumps = jumps + 1 return jumps # Driver code to test above methods start = point(1, 1) dest = point(-2, -1) lines = [] lines.append(line(1, 0, 0)) lines.append(line(0, 1, 0)) lines.append(line(1, 1, -2)) print(minJumpToReachDestination(start, dest, lines, 3)) # The code is contributed by Gautam goel (gautamgoel962)
Javascript
<script>
// Javascript program to find minimum jumps to reach
// a given destination from a given source
// To represent point in 2D space
class Point
{
constructor(x, y)
{
this.x = x;
this.y = y;
}
}
// To represent line of (ax + by + c)format
class line
{
constructor(a,b,c)
{
this.a = a;
this.b = b;
this.c = c;
}
}
// Returns 1 if evaluation is greater > 0,
// else returns -1
function evalPointOnLine(p, curLine){
var eval = curLine.a* p.x +
curLine.b * p.y +
curLine.c;
if (eval > 0)
return 1;
return -1;
}
// Returns minimum jumps to reach
// dest point from start point
function minJumpToReachDestination(start, dest, lines, N){
var jumps = 0;
for(var i = 0; i < N; i++){
// get sign of evaluation from point
// co-ordinate and line equation
var signStart = evalPointOnLine(start, lines[i]);
var signDest = evalPointOnLine(dest, lines[i]);
// if both evaluation are of opposite sign,
// increase jump by 1
if (signStart * signDest < 0)
jumps++;
}
return jumps;
}
// Driver code
let start = new Point(1, 1);
let dest = new Point(-2, -1);
let lines = new Array(3);
lines[0] = new line(1, 0, 0);
lines[1] = new line(0, 1, 0);
lines[2] = new line(1, 1, -2);
document.write(minJumpToReachDestination(start, dest, lines, 3));
// This code is contributed by shruti456rawal
</script>
Producción:
2
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA