Line Segment Intersection

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
 
#define char unsigned char
#define rep(i, a, b) for(int i=a; i< (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
 
#define LSOne(S) ((S) & -(S))
 
using namespace std;
// mt19937 rnd(239);
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> int sgn(T x) { return (T(0) < x) - (x < T(0)); }
typedef long double T;
typedef complex<T> pt;
#define X real()
#define Y imag()
 
template<class T>
istream& operator>> (istream& is, complex<T>& p) {
    T value;
    is >> value;
    p.real(value);
    is >> value;
    p.imag(value);
    return is;
}
 
typedef long long ll;
typedef long double ld;
 
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
 
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
 
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif
 
template<typename S, typename T = S> void chmin(S &s, T t) {s = s < t ? s : t;}
template<typename S, typename T = S> void chmax(S &s, T t) {s = s > t ? s : t;}
 
const int INF = 1e9; // 10^9 = 1B is < 2^31-1
const ll LLINF = 4e18; // 4*10^18 is < 2^63-1
const double EPS = 1e-9;
const ll MOD = 1e9+7;
 
T sq(pt p) {return p.X*p.X + p.Y*p.Y;}
T abs(pt p) {return sqrt(sq(p));}
bool half(pt p) { return p.Y > 0 || (p.Y == 0 && p.X < 0); } // check if p is on [pi, 0)
pt translate(pt v, pt p) { return v+p; } // translate 'v' with 'p'
pt scale(pt c, T factor, pt v) { return c+factor*(v-c); } // scale an object 'v' by a ratio 'factor' around a center 'c'
pt rot(pt p, T a) { return p*polar(1.0L, a); } // rotate around point 'p' with a rad 'a'
pt perp(pt p) { return {-p.Y, p.X}; } // rotate by 90 around the origin
pt linearTransfo(pt p, pt q, pt r, pt fp, pt fq) { return fp + (r-p) * (fq-fp) / (q-p); } // linear tranfomation f(r)=f(p)+(r-p)*((f(q)-f(p))/(q-p))
//T dot(pt v, pt w) { return v.X*w.X + v.Y*w.Y; } // dot product
T dot(pt v, pt w) {return (conj(v)*w).X;} // using trick
bool isPerp(pt v, pt w) { return dot(v,w) == 0; } // check if 'v' and 'w' are perpendicular
T angle(pt v, pt w) { return acos(clamp<T>(dot(v,w) / abs(v) / abs(w), -1.0, 1.0)); } // get angle between 'v' and 'w' vectors
//T cross(pt v, pt w) { return v.X*w.Y - v.Y*w.X; } // cross product of 'v' and 'w'
T cross(pt v, pt w) {return (conj(v)*w).Y;} // using trick
T orient(pt a, pt b, pt c) { return cross(b-a,c-a); } // returns 
                                                      //    positive if c is to the left of ab 
                                                      //    negative if c is to the left of ab
                                                      //    0 if a,b,c are co-linear
bool inAngle(pt a, pt b, pt c, pt p) { // check if p is in angle formed by bAc
    assert(orient(a,b,c) != 0);
    if (orient(a,b,c) < 0) swap(b,c);
    return orient(a,b,p) >= 0 && orient(a,c,p) <= 0;
}
T orientedAngle(pt a, pt b, pt c) { // TODO
    if (orient(a,b,c) >= 0)
    return angle(b-a, c-a);
    else
    return 2*M_PI - angle(b-a, c-a);
}
bool isConvex(vector<pt> p) { // check if polygon P is convex
    bool hasPos=false, hasNeg=false;
    for (int i=0, n=p.size(); i<n; i++) {
    int o = orient(p[i], p[(i+1)%n], p[(i+2)%n]);
    if (o > 0) hasPos = true;
    if (o < 0) hasNeg = true;
    }
    return !(hasPos && hasNeg);
}
void polarSort(vector<pt> &v) { // polar sort around the origin with closer to origin first
    sort(v.begin(), v.end(), [&](pt a, pt b) {
        if(half(a)<half(b)) return true;
        if(0.0L<cross(a,b)) return true;
        return sq(a)<sq(b);
    });
}
void polarSortAround(pt o, vector<pt> &v) { // polar sort around o with closer to origin first
    sort(v.begin(), v.end(), [&](pt a, pt b) {
        if(half(b-o)<half(a-o)) return true;
        return 0.0L<cross(a-o, b-o);
    });
}
struct line {
    pt v; T c; // From direction vector v and offset c
    line(pt v, T c) : v(v), c(c) {} // From equation ax+by=c
    line(T a, T b, T c) : v(pt{b,-a}), c(c) {} // From points P and Q
    line(pt p, pt q) : v(q-p), c(cross(v,p)) {}
 
    T side(pt p) {return cross(v,p)-c;} // which side of a line point p lies on
    T dist(pt p) {return abs(side(p)) / abs(v);} // distance between point p and the line
    T sqDist(pt p) {return side(p)*side(p) / (T)sq(v);} // square distance
    line perpThrough(pt p) {return {p, p + perp(v)};} // perpendicular line that goes through p
    bool cmpProj(pt p, pt q) {return dot(v,p) < dot(v,q);} // order of two points in order of the line
    line translate(pt t)  {return {v, c + cross(v,t)};} // translate line with vector 't'
    line shiftLeft(T dist)  {return {v, c + dist*abs(v)};} // line that is shifted by 'dist' to the left of the line
    pt proj(pt p) {return p - perp(v)*side(p)/sq(v);} // point on line that is closest to 'p'
    pt refl(pt p)  {return p - perp(v)*2.0L*side(p)/sq(v);} // reflection of point 'p' around the line
};
bool inter(line l1, line l2, pt &out) { // return true iff lines l1 and l2 are not parallel and saves to 'out' the point of intersection
    T d = cross(l1.v, l2.v);
    if (d == 0) return false;
    out = (l2.v*l1.c - l1.v*l2.c) / d; // requires floating-point coordinates
    return true;
}
line bisector(line l1, line l2, bool interior) { // bisector line
    assert(cross(l1.v, l2.v) != 0); // l1 and l2 cannot be parallel!
    T sign = interior ? 1 : -1;
    return {l2.v/abs(l2.v) + l1.v/abs(l1.v) * sign, l2.c/abs(l2.v) + l1.c/abs(l1.v) * sign};
}
bool inDisk(pt a, pt b, pt p) { // check if 'p' is inside of disc with diameter ab
    return dot(a-p, b-p) <= 0;
}
bool onSegment(pt a, pt b, pt p) { // check if 'p' is on segment ab
    return orient(a,b,p) == 0 && inDisk(a,b,p);
}
bool properInter(pt a, pt b, pt c, pt d, pt &out) { // intersection is one single point which is not an endpoint of either segment
                                                    // returns true iff there is point of intersection and saves to 'out' the point of intersection
    T oa = orient(c,d,a),
    ob = orient(c,d,b),
    oc = orient(a,b,c),
    od = orient(a,b,d);
    // Proper intersection exists iff opposite signs
    if (oa*ob < 0 && oc*od < 0) {
        out = (a*ob - b*oa) / (ob-oa);
        return true;
    }
    return false;
}
struct cmpX {
    bool operator()(const pt &a, const pt &b) const {
        return make_pair(a.X, a.Y) < make_pair(b.X, b.Y);
    }
};
set<pt,cmpX> inters(pt a, pt b, pt c, pt d) { // general intersection
                                              // returns set of points
    pt out;
    if (properInter(a,b,c,d,out)) return {out};
    set<pt,cmpX> s;
    if (onSegment(c,d,a)) s.insert(a);
    if (onSegment(c,d,b)) s.insert(b);
    if (onSegment(a,b,c)) s.insert(c);
    if (onSegment(a,b,d)) s.insert(d);
    return s;
}
T segPoint(pt a, pt b, pt p) { // return min distance from 'p' to segment ab
    if (a != b) {
        line l(a,b);
        if (l.cmpProj(a,p) && l.cmpProj(p,b)) // if closest to projection
        return l.dist(p); // output distance to line
    }
    return min(abs(p-a), abs(p-b)); // otherwise distance to A or B
}
T segSeg(pt a, pt b, pt c, pt d) { // returns min distance between two segments ab and cd
    pt dummy;
    if (properInter(a,b,c,d,dummy)) return 0;
    return min({segPoint(a,b,c), segPoint(a,b,d), segPoint(c,d,a), segPoint(c,d,b)});
}
T areaTriangle(pt a, pt b, pt c) { // area of triangle abc
    return abs(cross(b-a, c-a)) / 2.0L;
}
T areaPolygon(vector<pt> p) { // area of polygon p
    T area = 0.0;
    for (int i = 0, n = p.size(); i < n; i++) {
        area += cross(p[i], p[(i+1)%n]); // wrap back to 0 if i == n-1
    }
    return abs(area) / 2.0L;
}
bool above(pt a, pt p) { // true if P at least as high as A (blue part)
    return p.Y >= a.Y;
}
bool crossesRay(pt a, pt p, pt q) { // check if [PQ] crosses ray from A
    return (above(a,q) - above(a,p)) * orient(a,p,q) > 0;
}
bool inPolygon(vector<pt> p, pt a, bool strict = true) { // if strict, returns false when A is on the boundary
   int numCrossings = 0;
    for (int i = 0, n = p.size(); i < n; i++) {
        if (onSegment(p[i], p[(i+1)%n], a)) return !strict;
        numCrossings += crossesRay(a, p[i], p[(i+1)%n]);
    }
    return numCrossings & 1; // inside if odd number of crossings
}
T angleTravelled(pt a, pt p, pt q) { 
    // remainder ensures the value is in [-pi,pi]
    return remainder(arg(q-a) - arg(p-a), 2*M_PI);
}
int windingNumber(vector<pt> p, pt a) { // NaN if point on the edge
    T ampli = 0;
    for (int i = 0, n = p.size(); i < n; i++)
    ampli += angleTravelled(a, p[i], p[(i+1)%n]);
    return round(ampli / (2*M_PI));
}
pt circumCenter(pt a, pt b, pt c) {
    b = b-a, c = c-a; // consider coordinates relative to A
    assert(cross(b,c) != 0); // no circumcircle if A,B,C aligned
    return a + perp(b*sq(c) - c*sq(b))/cross(b,c)/2.0L;
}
int circleLine(pt o, T r, line l, pair<pt,pt> &out) { // returns number of intersections of line 'l' and the circle with center 'o' and radius 'r', saves points of intersection to 'out'
    T h2 = r*r - l.sqDist(o);
    if (h2 >= 0) { // the line touches the circle
        pt p = l.proj(o); // point P
        pt h = l.v*sqrt(h2)/abs(l.v); // vector parallel to l, of length h
        out = {p-h, p+h};
    }
    return 1 + sgn(h2);
}
int circleCircle(pt o1, T r1, pt o2, T r2, pair<pt,pt> &out) { // returns number of intersections of two circles, saves points of intersection to 'out'
    pt d=o2-o1; T d2=sq(d);
    if (d2 == 0) {assert(r1 != r2); return 0;} // concentric circles
    T pd = (d2 + r1*r1 - r2*r2)/2; // = |O_1P| * d
    T h2 = r1*r1 - pd*pd/d2; // = hˆ2
    if (h2 >= 0) {
        pt p = o1 + d*pd/d2, h = perp(d)*sqrt(h2/d2);
        out = {p-h, p+h};
    }
    return 1 + sgn(h2);
}
int tangents(pt o1, T r1, pt o2, T r2, bool inner, vector<pair<pt,pt>> &out) { // returns tangents to two circles, saves it to 'out' the points on circles 
    if (inner) r2 = -r2;
    pt d = o2-o1;
    T dr = r1-r2, d2 = sq(d), h2 = d2-dr*dr;
    if (d2 == 0 || h2 < 0) {assert(h2 != 0); return 0;}
    for (T sign : {-1,1}) {
        pt v = (d*dr + perp(d)*sqrt(h2)*sign)/d2;
        out.push_back({o1 + v*r1, o2 + v*r2});
    }
    return 1 + (h2 > 0);
}
 
int solve() {
    pt a,b,c,d; std::cin >> a >> b >> c >> d;
    cout << (inters(a,b,c,d).size()!=0 ? "YES" : "NO") << endl;
    
    return 0;
}
 
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1;
    cin >> TET;
    for (int i = 1; i <= TET; i++) {
        #ifdef ONPC
            cout << "TEST CASE#" << i << endl;
        #endif
        
        if (solve()) {
            break;
        }
 
        #ifdef ONPC
            cout << "__________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
    #endif
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED