Line Segment Intersection

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

#define int long long
#define endl '\n'
#define Point complex<int>
#define X real()
#define Y imag()

int cross_product(Point A, Point B, Point C) {
    return (conj(B - A) * (C - A)).Y;
}

bool compare_points(const Point &a, const Point &b) {
    return (a.X == b.X) ? (a.Y < b.Y) : (a.X < b.X);
}

bool is_mid_point(Point A, Point B, Point C) {
    vector<Point> v = {A, B, C};
    sort(v.begin(), v.end(), compare_points);
    return (v[1] == C);
}

int sign(int x) {
    return (x > 0) - (x < 0);
}

bool do_intersect(Point A, Point B, Point C, Point D) {
    int crossProduct1 = cross_product(A, B, C);
    int crossProduct2 = cross_product(A, B, D);
    int crossProduct3 = cross_product(C, D, A);
    int crossProduct4 = cross_product(C, D, B);
    if (crossProduct1 == 0 && is_mid_point(A, B, C)) return true;
    if (crossProduct2 == 0 && is_mid_point(A, B, D)) return true;
    if (crossProduct3 == 0 && is_mid_point(C, D, A)) return true;
    if (crossProduct4 == 0 && is_mid_point(C, D, B)) return true;
    if (sign(crossProduct1) != sign(crossProduct2) && sign(crossProduct3) != sign(crossProduct4))
        return true;
    return false;
}

signed main() {

    int t;
    cin >> t;

    vector<vector<Point>> points(t, vector<Point>(4));

    for (int i = 0; i < t; i++) {
        int x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

        points[i][0] = {x1, y1};
        points[i][1] = {x2, y2};
        points[i][2] = {x3, y3};
        points[i][3] = {x4, y4};
    }

    for (auto& point : points) {
        Point A = point[0];
        Point B = point[1];
        Point C = point[2];
        Point D = point[3];
        cout << (do_intersect(A, B, C, D) ? "YES" : "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