Given N lines and one starting point and destination point in 2-dimensional space. These N lines divide the space into some blocks. We need to print the minimum number of jumps to reach destination point from starting point. We can jump from one block to other block only if they share a side. Examples:
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.
We can solve this problem using a property of lines and points which is stated as, If we put two points in line equation then they will have same sign i.e. positive-positive or negative-negative of evaluated value if both points lies on the same side of line, in case of different sign i.e. positive-negative they will lie on different side of line. Now we can use above property to solve this problem, For each line, we will check if start and destination point lie on the same side or not. If they lie to the different side of a line then that line must be jumped to come closer. As in above diagram start point and the destination point are on the same side of x + y – 2 = 0 line, so that line need not to be jumped, rest two lines need to be jumped because both points lies on opposite side. Finally, we will check the sign of evaluation of points with respect to each line and we will increase our jump count whenever we found opposite signs. Total time complexity of this problem will be linear.
The step-by-step approach of the above idea:
- Define a struct ‘point‘ to represent a point in 2D space with x and y coordinates.
- Define a struct ‘line‘ to represent a line in the form of ‘ax + by + c‘.
- Define a function ‘evalPointOnLine‘ to evaluate if the given point lies on the given line.
- Define a function ‘minJumpToReachDestination‘ that takes a start point, a destination point, an array of lines, and the number of lines as inputs.
- Initialize jumps to 0.
- For each line in the array, evaluate the start and destination points on the line using ‘evalPointOnLine‘.
- If the evaluations have opposite signs, increment jumps by 1.
- Return the final value of jumps.
- In the main function, define a start point, a destination point, an array of lines, and the number of lines.
Call the function ‘minJumpToReachDestination‘ with these inputs and print the result.
Below is the implementation:
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 spacestruct point{ int x, y; point(int x, int y) : x(x), y(y) {}};// To represent line of (ax + by + c)formatstruct 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 -1int 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 pointint 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 methodsint 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 sourceclass GFG{// To represent point in 2D spacestatic 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)formatstatic 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 -1static 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 pointstatic 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 sourceusing System;class GFG{// To represent point in 2D spaceclass point{ public int x, y; public point(int x, int y) { this.x = x; this.y = y; } };// To represent line of (ax + by + c)formatclass 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 -1static 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 pointstatic 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 spaceclass point: def __init__(self, x, y): self.x = x self.y = y# To represent line of (ax + by + c)formatclass 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 -1def 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 pointdef 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 methodsstart = 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> |
Output:
2
Time Complexity: O(1)
Auxiliary Space: O(1)
This article is contributed by Aarti_Rathi and Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
