Submission details
Task:Line Intersections
Sender:aalto26jh_024
Submission time:2026-11-09 19:08:55 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.00 sdetails
#70.00 sdetails
#80.00 sdetails
#90.00 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails
#130.00 sdetails
#140.00 sdetails
#150.00 sdetails
#160.00 sdetails
#170.00 sdetails
#180.00 sdetails
#190.00 sdetails
#200.00 sdetails
#210.00 sdetails
#220.00 sdetails
#230.00 sdetails
#240.00 sdetails
#250.00 sdetails
#260.00 sdetails
#270.00 sdetails
#280.00 sdetails
#290.00 sdetails
#300.00 sdetails
#310.00 sdetails
#320.00 sdetails
#330.00 sdetails
#340.00 sdetails
#350.00 sdetails
#360.00 sdetails
#370.01 sdetails
#380.01 sdetails
#390.01 sdetails
#400.01 sdetails

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Point {
    ll x, y; // Upgraded to long long to prevent ANY intermediate math overflow
    void read() { cin >> x >> y; }
};

// Returns 1 if counter-clockwise, -1 if clockwise, 0 if collinear
int ccw(Point a, Point b, Point c) {
    ll area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (area > 0) return 1;
    if (area < 0) return -1;
    return 0;
}

// Checks if point p lies exactly on the segment ab
bool on_segment(Point p, Point a, Point b) {
    return p.x >= min(a.x, b.x) && p.x <= max(a.x, b.x) &&
           p.y >= min(a.y, b.y) && p.y <= max(a.y, b.y) &&
           ccw(a, b, p) == 0;
}

void lineintersect(Point p1, Point p2, Point p3, Point p4) {
    int cp1 = ccw(p1, p2, p3);
    int cp2 = ccw(p1, p2, p4);
    int cp3 = ccw(p3, p4, p1);
    int cp4 = ccw(p3, p4, p2);

    // General case: The segments strictly straddle each other's lines
    if (cp1 != cp2 && cp3 != cp4) {
        cout << "YES\n";
        return;
    }

    // Collinear, degenerate, or touching endpoint cases:
    // If any endpoint lies exactly on the other segment, they intersect.
    if (on_segment(p3, p1, p2) || on_segment(p4, p1, p2) ||
        on_segment(p1, p3, p4) || on_segment(p2, p3, p4)) {
        cout << "YES\n";
        return;
    }

    cout << "NO\n";
}

int main(){
    // Fast I/O since T can be up to 10^5
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    if (cin >> T) {
        while(T--){
            Point P[4];
            for(int i = 0; i < 4; i++) 
                P[i].read();
            lineintersect(P[0], P[1], P[2], P[3]);
        }
    }
    return 0;
}

Test details

Test 1

Verdict:

input
1
1 1 -1 1

correct output
0

user output
NO

Feedback: Incorrect character on line 1 col 1: expected "0", got "NO"

Test 2

Verdict:

input
1
-1 1 1 1

correct output
0

user output
NO

Feedback: Incorrect character on line 1 col 1: expected "0", got "NO"

Test 3

Verdict:

input
2
2 1 -2 1
-1 2 -2 2

correct output
0

user output
NO
NO

Feedback: Output is longer than expected

Test 4

Verdict:

input
2
-2 2 2 2
-1 0 -2 0

correct output
0

user output
NO
NO

Feedback: Output is longer than expected

Test 5

Verdict:

input
3
3 2 -3 2
-1 3 -2 3
-3 -1 -2 -1

correct output
0

user output
NO
NO
NO

Feedback: Output is longer than expected

Test 6

Verdict:

input
3
-3 3 2 3
-1 0 -3 0
-1 2 -1 -1

correct output
2

user output
NO
YES
YES

Feedback: Output is longer than expected

Test 7

Verdict:

input
4
4 2 -4 2
-2 4 -3 4
-4 -1 -3 -1
-1 0 3 0

correct output
0

user output
NO
NO
NO
NO

Feedback: Output is longer than expected

Test 8

Verdict:

input
4
-4 3 3 3
-1 4 4 4
-4 1 -1 1
-1 0 -1 -2

correct output
3

user output
NO
NO
NO
NO

Feedback: Output is longer than expected

Test 9

Verdict:

input
5
5 2 -5 2
-2 5 -4 5
-4 -1 -3 -1
-2 0 4 0
...

correct output
0

user output
NO
NO
NO
NO
NO

Feedback: Output is longer than expected

Test 10

Verdict:

input
5
-5 4 4 4
-1 5 5 5
-5 1 -1 1
-2 0 -2 -2
...

correct output
6

user output
NO
NO
NO
NO
NO

Feedback: Output is longer than expected

Test 11

Verdict:

input
5
5 -2 5 -3
-5 -5 -5 -1
5 1 -4 1
1 -1 1 0
...

correct output
6

user output
NO
NO
NO
NO
NO

Feedback: Output is longer than expected

Test 12

Verdict:

input
6
6 3 -6 3
-3 6 -5 6
-5 -1 -4 -1
-2 2 -1 2
...

correct output
5

user output
NO
NO
YES
YES
YES
...

Feedback: Output is longer than expected

Test 13

Verdict:

input
6
-6 5 4 5
-2 6 0 6
1 -1 3 -1
0 0 -3 0
...

correct output
8

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 14

Verdict:

input
7
7 3 6 3
-6 -3 7 -3
-4 -6 -2 -6
-2 -2 3 -2
...

correct output
0

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 15

Verdict:

input
7
-7 6 5 6
-2 7 0 7
2 -2 4 -2
0 0 -3 0
...

correct output
10

user output
NO
NO
NO
YES
YES
...

Feedback: Output is longer than expected

Test 16

Verdict:

input
10
10 5 9 5
-8 -4 10 -4
-6 -9 -2 -9
-2 -3 4 -3
...

correct output
9

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 17

Verdict:

input
10
-7 -10 9 -10
9 -1 9 0
-4 -4 -7 -4
4 3 -8 3
...

correct output
24

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 18

Verdict:

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

correct output
24

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 19

Verdict:

input
10
8 1 8 -7
7 5 7 2
2 -6 2 -8
-6 -10 -6 4
...

correct output
24

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 20

Verdict:

input
10
-9 8 7 8
-3 9 10 9
-9 2 -2 2
-3 0 -3 -4
...

correct output
24

user output
NO
NO
NO
NO
YES
...

Feedback: Output is longer than expected

Test 21

Verdict:

input
10
9 -4 9 -6
-9 -10 -9 -3
10 2 -8 2
2 -2 2 1
...

correct output
21

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 22

Verdict:

input
10
-6 6 -4 6
10 5 -1 5
-4 1 -4 -5
-9 -9 -9 -2
...

correct output
24

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 23

Verdict:

input
50
50 22 44 22
-38 -20 50 -20
-27 -41 -10 -41
-11 -16 17 -16
...

correct output
576

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 24

Verdict:

input
50
-32 -48 44 -48
45 -7 45 -2
-18 -17 -35 -17
20 12 -38 12
...

correct output
621

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 25

Verdict:

input
50
-43 21 -43 34
-38 1 7 1
-6 40 -6 -49
-46 -30 -25 -30
...

correct output
616

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 26

Verdict:

input
50
40 5 40 -33
36 22 36 11
10 -29 10 -36
-28 -50 -28 20
...

correct output
624

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 27

Verdict:

input
50
-45 37 33 37
-14 42 48 42
-41 11 -10 11
-15 2 -15 -1
...

correct output
576

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 28

Verdict:

input
100
100 44 87 44
-75 -40 100 -40
-53 -82 -21 -82
-23 -31 34 -31
...

correct output
2464

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 29

Verdict:

input
100
-63 -95 87 -95
90 -13 90 -3
-36 -34 -69 -34
40 24 -76 24
...

correct output
2475

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 30

Verdict:

input
100
-86 42 -86 68
-76 2 14 2
-13 80 -13 -97
-92 -59 -51 -59
...

correct output
2500

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 31

Verdict:

input
100
81 9 81 -66
71 43 71 22
20 -57 20 -72
-55 -99 -55 40
...

correct output
2464

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 32

Verdict:

input
100
-89 75 67 75
-27 84 96 84
-82 22 -21 22
-29 4 -29 -3
...

correct output
2491

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 33

Verdict:

input
200
199 88 173 88
-149 -79 200 -79
-106 -163 -41 -163
-45 -62 68 -62
...

correct output
9984

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 34

Verdict:

input
200
-126 -190 173 -190
180 -26 180 -6
-72 -68 -139 -68
80 48 -152 48
...

correct output
9919

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 35

Verdict:

input
200
-172 83 -172 136
-152 4 28 4
-25 159 -25 -193
-184 -117 -101 -117
...

correct output
9991

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 36

Verdict:

input
200
161 19 161 -131
143 86 143 44
39 -114 39 -144
-110 -198 -110 80
...

correct output
9999

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 37

Verdict:

input
10000
9944 4407 8652 4407
-7438 -3954 9981 -3954
-5278 -8154 -2068 -8154
-2242 -3089 3395 -3089
...

correct output
24992431

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 38

Verdict:

input
10000
-6299 -9482 8631 -9482
8955 -1294 8955 -305
-3589 -3393 -6912 -3393
3977 2386 -7601 2386
...

correct output
24999775

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 39

Verdict:

input
10000
-8586 4163 -8586 6799
-7574 217 1386 217
-1259 7926 -1259 -9626
-9188 -5855 -5042 -5855
...

correct output
24999856

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected

Test 40

Verdict:

input
10000
8013 945 8013 -6546
7113 4297 7113 2181
1951 -5678 1951 -7171
-5510 -9876 -5510 3969
...

correct output
24999996

user output
NO
NO
NO
NO
NO
...

Feedback: Output is longer than expected