Line Segment Intersection

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

typedef complex<long long> P;
#define X real()
#define Y imag()

int orientation(P p, P q, P r) {
    long long val = (q.Y - p.Y) * (r.X - q.X) - (q.X - p.X) * (r.Y - q.Y);
    if (val == 0) return 0;
    return (val > 0) ? 1 : 2;
}

bool onSegment(P p, P q, P r) {
    return (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));
}

bool doIntersect(P p1, P q1, P p2, P 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) ||
    (o1 == 0 && onSegment(p1, p2, q1)) ||
    (o2 == 0 && onSegment(p1, q2, q1)) ||
    (o3 == 0 && onSegment(p2, p1, q2)) ||
    (o4 == 0 && onSegment(p2, q1, q2)))
        return true;

    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

    int t;
    cin >> t;
    while (t--) {
        P p1, q1, p2, q2;
        long long x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        p1 = P(x1, y1);
        q1 = P(x2, y2);
        p2 = P(x3, y3);
        q2 = P(x4, y4);

        if (doIntersect(p1, q1, p2, q2)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    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