Submission details
Task:Line Segment Intersection
Sender:aalto26jh_022
Submission time:2026-11-11 16:01:17 +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;

struct Point {
    long long x, y;
};

long long cross_product(Point p, Point q, Point r) {
    return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
}

int sign(long long val) {
    if (val > 0) return 1;
    if (val < 0) return -1;
    return 0;
}

bool onSegment(Point p, Point q, Point r) {
    return q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
           q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    if (!(cin >> t)) return 0;
    
    while (t--) {
        Point A, B, C, D;
        cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y;

        int cp1 = sign(cross_product(A, B, C));
        int cp2 = sign(cross_product(A, B, D));
        int cp3 = sign(cross_product(C, D, A));
        int cp4 = sign(cross_product(C, D, B));

        if (cp1 != cp2 && cp3 != cp4) {
            cout << "YES\n";
        } 
        else if (cp1 == 0 && onSegment(A, C, B)) {
            cout << "YES\n";
        } else if (cp2 == 0 && onSegment(A, D, B)) {
            cout << "YES\n";
        } else if (cp3 == 0 && onSegment(C, A, D)) {
            cout << "YES\n";
        } else if (cp4 == 0 && onSegment(C, B, D)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

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