Given the coordinates of the endpoints(p1,q1, and p2,q2) of the two line segments. Check if they intersect or not. If the Line intersects return true otherwise return false.
Examples
Input: p1=(1,1), q1=(10,1), p2=(1,2), q2=(10,2) Output: false Explanation: The two line segments formed by p1-q1 and p2-q2 do not intersect.
Input: p1=(10,0), q1=(0,10), p2=(0,0), q2=(10,10) Output: true Explanation: The two line segments formed by p1-q1 and p2-q2 intersect.
Expected Time Complexity: O(1)
Expected Auxillary Space: O(1)
Constraints:
-106<=X,Y(for all points)<=106
Approach 01:
-
C++
-
Python
#include <iostream> #include <algorithm> #include <string> using namespace std; class Solution { public: // Function to find the orientation of the triplet (p, q, r) int orientation(const int p[], const int q[], const int r[]) { long long val = static_cast<long long>(q[1] - p[1]) * (r[0] - q[0]) - static_cast<long long>(q[0] - p[0]) * (r[1] - q[1]); if (val == 0) return 0; // collinear return (val > 0) ? 1 : 2; // clock or counterclockwise } // Function to check if point q lies on segment pr bool onSegment(const int p[], const int q[], const int r[]) { if (q[0] <= max(p[0], r[0]) && q[0] >= min(p[0], r[0]) && q[1] <= max(p[1], r[1]) && q[1] >= min(p[1], r[1])) return true; return false; } string doIntersect(const int p1[], const int q1[], const int p2[], const int q2[]) { // Find the four orientations needed for the general and special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return "true"; // Special Cases // p1, q1 and p2 are collinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return "true"; // p1, q1 and q2 are collinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return "true"; // p2, q2 and p1 are collinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return "true"; // p2, q2 and q1 are collinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return "true"; // Doesn't fall in any of the above cases return "false"; } };
class Solution: def orientation(self, p, q, r): val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]) if val == 0: return 0 # collinear return 1 if val > 0 else 2 # clock or counterclockwise def onSegment(self, p, q, r): if q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and \ q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1]): return True return False def doIntersect(self, p1, q1, p2, q2): # Find the four orientations needed for the general and special cases o1 = self.orientation(p1, q1, p2) o2 = self.orientation(p1, q1, q2) o3 = self.orientation(p2, q2, p1) o4 = self.orientation(p2, q2, q1) # General case if o1 != o2 and o3 != o4: return "true" # Special Cases # p1, q1 and p2 are collinear and p2 lies on segment p1q1 if o1 == 0 and self.onSegment(p1, p2, q1): return "true" # p1, q1 and q2 are collinear and q2 lies on segment p1q1 if o2 == 0 and self.onSegment(p1, q2, q1): return "true" # p2, q2 and p1 are collinear and p1 lies on segment p2q2 if o3 == 0 and self.onSegment(p2, p1, q2): return "true" # p2, q2 and q1 are collinear and q1 lies on segment p2q2 if o4 == 0 and self.onSegment(p2, q1, q2): return "true" # Doesn't fall in any of the above cases return "false"