Submission details
Task:Line Segment Intersection
Sender:aalto26jh_007
Submission time:2026-11-09 15:03:19 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.32 sdetails
#2ACCEPTED0.38 sdetails
#3ACCEPTED0.48 sdetails
#40.57 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails

Code

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <bits/stdc++.h>

using namespace std;


bool doIntersect(int p1[], int q1[], int p2[], int q2[])
{
    // Equation of line 1:
    // a1*x + b1*y = c1
    long long a1 = q1[1] - p1[1];
    long long b1 = p1[0] - q1[0];
    long long c1 = a1 * p1[0] + b1 * p1[1];

    // Equation of line 2:
    // a2*x + b2*y = c2
    long long a2 = q2[1] - p2[1];
    long long b2 = p2[0] - q2[0];
    long long c2 = a2 * p2[0] + b2 * p2[1];

    // Determinant of the two line equations.
    // If it is 0, the lines are parallel or collinear.
    long long det = a1 * b2 - a2 * b1;

    // Handle parallel or collinear lines.
    if (det == 0)
    {
        // The lines are parallel but different.
        if (a1 * p2[0] + b1 * p2[1] != c1)
            return false;

        // The lines are collinear.
        // Check whether their bounding boxes overlap.
        return !(max(p1[0], q1[0]) < min(p2[0], q2[0]) || max(p2[0], q2[0]) < min(p1[0], q1[0]) ||
                 max(p1[1], q1[1]) < min(p2[1], q2[1]) || max(p2[1], q2[1]) < min(p1[1], q1[1]));
    }

    // Calculate the numerator of the intersection point.
    // x = xNum / det
    // y = yNum / det
    long long xNum = b2 * c1 - b1 * c2;
    long long yNum = a1 * c2 - a2 * c1;

    // Find the bounding box of the first segment.
    long long minX1 = min(p1[0], q1[0]);
    long long maxX1 = max(p1[0], q1[0]);
    long long minY1 = min(p1[1], q1[1]);
    long long maxY1 = max(p1[1], q1[1]);

    // Find the bounding box of the second segment.
    long long minX2 = min(p2[0], q2[0]);
    long long maxX2 = max(p2[0], q2[0]);
    long long minY2 = min(p2[1], q2[1]);
    long long maxY2 = max(p2[1], q2[1]);

    // Make the denominator positive so that
    // all comparisons below use the same direction.
    if (det < 0)
    {
        det = -det;
        xNum = -xNum;
        yNum = -yNum;
    }

    // Check whether the intersection point lies
    // inside both line segments.
    return xNum >= minX1 * det && xNum <= maxX1 * det && yNum >= minY1 * det && yNum <= maxY1 * det &&
           xNum >= minX2 * det && xNum <= maxX2 * det && yNum >= minY2 * det && yNum <= maxY2 * det;
}

int main()
{
    int p1[] = {0, 0};
    int q1[] = {0, 0};

    int p2[] = {0, 0};
    int q2[] = {0, 0};

    int n_checks;
    cin >> n_checks;

    for(int i = 0; i < n_checks; ++i)
    {
        cin >> p1[0] >> p1[1];
        cin >> q1[0] >> q1[1];
        cin >> p2[0] >> p2[1];
        cin >> q2[0] >> q2[1];
        bool res = doIntersect(p1, q1, p2, q2);
        cout << (res ? "YES" : "NO") << '\n';
    }



    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:

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 1: expected "YES", got "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