Line Segment Intersection

#include <iostream>
using namespace std;

int orientation(pair<long long, long long> p, pair<long long, long long> q, pair<long long, long long> r) {
    long long val = (q.second - p.second) * (r.first - q.first) - (q.first - p.first) * (r.second - q.second);
    if (val == 0) return 0;         
    return (val > 0) ? 1 : 2;       
}

bool onSegment(pair<long long, long long> p, pair<long long, long long> q, pair<long long, long long> r) {
    return q.first <= max(p.first, r.first) && q.first >= min(p.first, r.first) &&
           q.second <= max(p.second, r.second) && q.second >= min(p.second, r.second);
}

bool doIntersect(pair<long long, long long> p1, pair<long long, long long> q1, pair<long long, long long> p2, pair<long long, long long> q2) {
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4) return true;

    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false;
}

int main() {
    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;

        pair<long long, long long> p1 = {x1, y1};
        pair<long long, long long> q1 = {x2, y2};
        pair<long long, long long> p2 = {x3, y3};
        pair<long long, long long> q2 = {x4, y4};

        if (doIntersect(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