Line Segment Intersection

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

struct pt{ ll x; ll y; };
pt operator+(const pt& a, const pt& b){ return pt{.x=a.x+b.x, .y=a.y+b.y}; };
pt operator-(const pt& a, const pt& b){ return pt{.x=a.x-b.x, .y=a.y-b.y}; };
bool operator==(const pt& a, const pt& b){ return a.x == b.x && a.y == b.y; };
ostream& operator<<(ostream& os, const pt& a){ return os << "(" << a.x << "," << a.y << ")"; }
ll cross(pt p1, pt p2){
    return p1.x*p2.y - p1.y*p2.x;
}
ll orient(pt p, pt q, pt r) {
    ll v = (q.x-p.x)*(r.y-p.y)-(q.y-p.y)*(r.x-p.x);
    if(v == 0) return 0;
    return (v > 0) ? 2:1;
}

bool on(const pt& a, const pt& b, const pt& c){
    return min(a.x,b.x)<=c.x&&c.x<=max(a.x,b.x)&&min(a.y,b.y)<=c.y&&c.y<=max(a.y,b.y);
}

bool inters(const pt& p1, const pt& q1, const pt& p2, const pt& q2){
    auto o1 = orient(p1, q1, p2);
    auto o2 = orient(p1, q1, q2);
    auto o3 = orient(p2, q2, p1);
    auto o4 = orient(p2, q2, q1);
    if(o1 != o2 && o3 != o4) return true;
    if(o1 == 0 && on(p1, p2, q1)) return true;
    if(o2 == 0 && on(p1, q2, q1)) return true;
    if(o3 == 0 && on(p2, p1, q2)) return true;
    if(o4 == 0 && on(p2, q1, q2)) return true;
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ull t;
    cin >> t;

    for(ull 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;

        // ll cp1 = orient(p3,p4,p1);
        // ll cp2 = orient(p3,p4,p2);
        // ll cp3 = orient(p1,p2,p3);
        // ll cp4 = orient(p1,p2,p4);

        // bool inter = (((cp1>0 && cp2<0) || (cp1<0 && cp2>0)) && ((cp3>0 && cp4<0) || (cp3<0 && cp4>0))) || ((cp1 == 0 || cp2 == 0) && (cp3 == 0 || cp4 == 0)) || p1 == p3 || p2 == p3 || p1 == p4 || p2 == p4 || (
        //     (cp1 == 0 && on(p3, p4, p1)) ||
        //     (cp2 == 0 && on(p3, p4, p2)) ||
        //     (cp3 == 0 && on(p1, p2, p3)) ||
        //     (cp4 == 0 && on(p1, p2, p4))
        // );
        bool inter = inters(p1, p2, p3, p4);
        // cout << p1 << " " << p2 << " " << p3 << " " << p4 << " " << inter << "\n";
        cout << (inter ? "YES\n" : "NO\n");
    }
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED