Line Segment Intersection

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define vout(x) for(int i=0;i<(long long)x.size();i++) printf("%lld ",x[i]);
#define REP(i,a,b) for (int i = a; i <= b; i++)

// g++ <filename>.cpp -g -Wall -Wextra -DDEBUG -o <executable>

// copied from: https://codeforces.com/blog/entry/79024
// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}

// === Debug macro ends here ===

struct pt {
    long long x, y;
    pt operator +(const pt &p) const {return pt{x + p.x, y + p.y};}
    pt operator -(const pt &p) const {return pt{x - p.x, y - p.y};}
    bool operator ==(const pt &p) {return x == p.x && y == p.y;}
    long long operator *(const pt &p) const {return x * p.y - y * p.x;}
    void print() {cout << "[" << x << "," << y << "]\n";}
    long long cross(const pt &a, const pt &b) const {
        return (a - *this) * (b - *this);
    }
};

void intersect(pt p1, pt p2, pt p3, pt p4) {
    
    // parallel
    if ((p2 - p1) * (p4 - p3) == 0) {

        if(p1.cross(p2, p3) == 0)
        {
            for(int i = 0; i < 2; i++)
            {
                if(max(p1.x, p2.x) < min(p3.x, p4.x) || max(p1.y, p2.y) < min(p3.y, p4.y)){
                    printf("NO\n");
                    return;
                }
                swap(p1, p3);
                swap(p2, p4);
            }
            printf("YES\n");
            return;
        }
    }

    // touching intersection
    if (p1 == p3 || p1 == p4 || p2 == p3 || p2 == p4) {
        cout << "YES\n";
        return;
    }

    // general intersection
    for (int i = 0; i < 2; i++) {

        int s1 = p1.cross(p2, p3);
        int s2 = p1.cross(p2, p4);

        if((s1 < 0 && s2 < 0) || (s1 > 0 && s2 > 0))
        {
            printf("NO\n");
            return;
        }
        swap(p1, p3);
        swap(p2, p4);
    }

    cout << "YES\n";
    return;
}

signed main() {
    
    int t;
    cin >> t;
    
    for (int i = 0; i < t; i++) {
        pt p1,p2,p3,p4;
        cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y>>p4.x>>p4.y;
    
        intersect(p1,p2,p3,p4);
    }

    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