Line Segment Intersection

#include <bits/stdc++.h>
using namespace std;

// Structure to represent a point
struct Point {
    long long x, y;
};

// Function to determine the orientation of ordered triplet (p, q, r)
// Returns 0 -> colinear, 1 -> clockwise, 2 -> counterclockwise
int orientation(const Point& p, const Point& q, const Point& r) {
    // Compute the determinant (cross product)
    long long val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0LL) return 0; // colinear
    return (val > 0LL) ? 1 : 2; // clockwise or counterclockwise
}

// Function to check if point q lies on segment pr
bool onSegment(const Point& p, const Point& q, const Point& r) {
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
        return true;
    return false;
}

// Function to check if two segments p1q1 and p2q2 intersect
bool segmentsIntersect(const Point& p1, const Point& q1, const Point& p2, const Point& q2) {
    // Find the four orientations needed for 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 colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    
    // p1, q1 and q2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    
    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    
    // p2, q2 and q1 are colinear 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;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    
    while(t--){
        long long x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        
        Point p1 = {x1, y1};
        Point q1 = {x2, y2};
        Point p2 = {x3, y3};
        Point q2 = {x4, y4};
        
        if(segmentsIntersect(p1, q1, p2, q2)){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }
    
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED