Submission details
Task:Line Segment Intersection
Sender:aalto26jh_030
Submission time:2026-11-11 12:49:53 +0200
Language:C++ (C++23)
Status:READY
Result:
Test results
testverdicttime
#10.08 sdetails
#20.08 sdetails
#30.10 sdetails
#40.12 sdetails
#50.00 sdetails
#6ACCEPTED0.00 sdetails

Code

#include <iostream>
#include <vector>

struct Point {
    long long x, y;
};

int crossProd(Point a, Point b, Point c) {
    long long val = (b.y - a.y) * (c.x - b.x) -
                    (b.x - a.x) * (c.y - b.y);
    if (val == 0) return 0;
    return (val > 0) ? 1 : 2;
}

bool onSegment(Point a, Point b, Point c) {
    return (b.x >= std::min(a.x, c.x) && b.x <= std::max(a.x, c.x) &&
            b.y >= std::min(a.y, c.y) && b.y <= std::max(a.y, c.y));
}

bool doIntersect(Point a, Point b, Point c, Point d) {
    int o1 = crossProd(a, b, c);
    int o2 = crossProd(a, b, d);
    int o3 = crossProd(c, d, a);
    int o4 = crossProd(c, d, b);
    if (o1 != 0 && o2 != 0 && o3 != 0 && o4 != 0 && 
        o1 != o2 && o3 != o4) {
        return true;
    }
    if (o1 == 0 && onSegment(a, c, b)) return true;
    if (o2 == 0 && onSegment(a, d, b)) return true;
    if (o3 == 0 && onSegment(c, a, d)) return true;
    if (o4 == 0 && onSegment(c, b, d)) return true;
    return false;
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    for (int i = 0; i < t; i++) {
        Point a, b, c , d;
        std::cin >> a.x >> a.y 
            >> b.x >> b.y
            >> c.x >> c.y
            >> d.x >> d.y;
        if (doIntersect(a, b, c, d)) std::cout << "Yes" << '\n';
        else std::cout << "NO" << '\n';
    }
}

Test details

Test 1

Verdict:

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
...

Feedback: Incorrect character on line 6 col 2: expected "YES", got "Yes"

Test 2

Verdict:

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

correct output
NO
NO
YES
NO
YES
...

user output
NO
NO
Yes
NO
Yes
...

Feedback: Incorrect character on line 3 col 2: expected "YES", got "Yes"

Test 3

Verdict:

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

correct output
YES
YES
NO
YES
YES
...

user output
Yes
Yes
NO
Yes
Yes
...

Feedback: Incorrect character on line 1 col 2: expected "YES", got "Yes"

Test 4

Verdict:

input
100000
788522666 939776556 -831492125...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Feedback: Incorrect character on line 11 col 2: expected "YES", got "Yes"

Test 5

Verdict:

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

correct output
YES

user output
Yes

Feedback: Incorrect character on line 1 col 2: expected "YES", got "Yes"

Test 6

Verdict: ACCEPTED

input
1
-1000000000 1000000000 9999999...

correct output
NO

user output
NO