Line Segment Intersection

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

typedef long long ll;

struct Point {
    ll x, y;
};

int orientation(const Point& p, const Point& q, const Point& r){
    ll val = (q.x - p.x)*(r.y - p.y) - (q.y - p.y)*(r.x - p.x);
    if(val == 0) return 0;
    return (val > 0) ? 1 : 2;
}

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;
}

bool doIntersect(const Point& p1, const Point& p2, const Point& p3, const Point& p4){
    int o1 = orientation(p1, p2, p3);
    int o2 = orientation(p1, p2, p4);
    int o3 = orientation(p3, p4, p1);
    int o4 = orientation(p3, p4, p2);
    if(o1 != o2 && o3 != o4)
        return true;
    if(o1 == 0 && onSegment(p1, p3, p2)) return true;
    if(o2 == 0 && onSegment(p1, p4, p2)) return true;
    if(o3 == 0 && onSegment(p3, p1, p4)) return true;
    if(o4 == 0 && onSegment(p3, p2, p4)) return true;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        Point p1, p2, p3, p4;
        cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y >> p4.x >> p4.y;
        if(doIntersect(p1, p2, p3, p4))
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED