Submission details
Task:Line Segment Intersection
Sender:aalto26jh_033
Submission time:2026-11-10 11:24:44 +0200
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.08 sdetails
#2ACCEPTED0.09 sdetails
#3ACCEPTED0.10 sdetails
#4ACCEPTED0.12 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails

Code

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

// debug
template<class T> ostream& operator<<(ostream&, const vector<T>&);
template<class T> ostream& operator<<(ostream&, const set<T>&);
template<class T> ostream& operator<<(ostream&, const multiset<T>&);
template<class K, class V> ostream& operator<<(ostream&, const map<K, V>&);
template<class T, size_t N> ostream& operator<<(ostream&, const array<T, N>&);
template<class A, class B> ostream& operator<<(ostream& os, const pair<A, B>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<class T>
void print_collection(ostream& os, const T& v) {
    os << "{";
    bool first = true;
    for (const auto& x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << "}";
}
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const set<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const multiset<T>& v) { print_collection(os, v); return os; }
template<class K, class V> ostream& operator<<(ostream& os, const map<K, V>& v) { print_collection(os, v); return os; }
template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N>& v) { print_collection(os, v); return os; }
#define dbg(x) cerr << #x << " = " << (x) << '\n'

using ll = long long;
constexpr int INF = 1'000'000'000; // 1e9
constexpr ll LINF = 1'000'000'000'000'000'000LL; // 1e18
constexpr int MOD = 1'000'000'007; // 1e9 + 7

inline ll add(ll a, ll b) { return (a + b) % MOD; }
inline ll sub(ll a, ll b) { return ((a - b) % MOD + MOD) % MOD; }
inline ll mul(ll a, ll b) { return (a * b) % MOD; }

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

ll crossProduct(P a, P b) {
    return (conj(a)*b).Y;
}

// positive -> left; negative -> right; 0 -> on line
int pointLocation(P p, P s1, P s2) {
    ll a = crossProduct(p-s1, p-s2);
    return a == 0 ? 0 : (a>0 ? 1 : -1);
}

bool onSegment(P p, P s1, P s2) {
    return pointLocation(p, s1, s2) == 0 && min(s1.X, s2.X) <= p.X && p.X <= max(s1.X, s2.X) && min(s1.Y, s2.Y) <= p.Y && p.Y <= max(s1.Y, s2.Y);
}

bool intersect(P a, P b, P c, P d) {
    int pl1 = pointLocation(c, a, b), pl2 = pointLocation(d, a, b), pl3 = pointLocation(a, c, d), pl4 = pointLocation(b, c, d);

    // case 1 or 2: same line or vertex contact
    if (
        (pl1 == 0 && onSegment(c, a, b)) ||
        (pl2 == 0 && onSegment(d, a, b)) ||
        (pl3 == 0 && onSegment(a, c, d)) ||
        (pl4 == 0 && onSegment(b, c, d))
    ) return true;

    // case 3: exactly one non vertex intersection
    return pl1 != pl2 && pl3 != pl4;
}

void solve() {
    int N;
    cin >> N;

    int x,y;
    for(int i=0;i<N;++i) {
        cin >> x >> y;
        P p1 = {x,y};
        cin >> x >> y;
        P p2 = {x,y};
        cin >> x >> y;
        P p3 = {x,y};
        cin >> x >> y;
        P p4 = {x,y};

        cout << (intersect(p1, p2, p3, p4) ? "YES" : "NO") << '\n';
    }
    
}

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

    solve();

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
100000
9 7 1 8 8 -5 0 2
10 1 -1 2 -4 1 -7 3
10 2 -8 6 1 2 2 -1
-10 1 9 -7 4 -3 -5 0
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 2

Verdict: ACCEPTED

input
100000
81 745 -967 768 -451 -490 -454...

correct output
NO
NO
YES
NO
YES
...

user output
NO
NO
YES
NO
YES
...

Test 3

Verdict: ACCEPTED

input
100000
492853 -452834 -657156 -282543...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...

Test 4

Verdict: ACCEPTED

input
100000
788522666 939776556 -831492125...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Test 5

Verdict: ACCEPTED

input
1
1 6 6 6 4 4 1000000000 1000000...

correct output
YES

user output
YES

Test 6

Verdict: ACCEPTED

input
1
-1000000000 1000000000 9999999...

correct output
NO

user output
NO