Submission details
Task:Line Intersections
Sender:aalto26jh_012
Submission time:2026-11-06 13:43:14 +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.06 sdetails
#70.00 sdetails
#80.06 sdetails
#90.00 sdetails
#100.06 sdetails
#110.06 sdetails
#120.06 sdetails
#130.06 sdetails
#140.00 sdetails
#150.06 sdetails
#160.06 sdetails
#170.06 sdetails
#180.06 sdetails
#190.06 sdetails
#200.06 sdetails
#210.06 sdetails
#220.06 sdetails
#230.06 sdetails
#240.06 sdetails
#250.06 sdetails
#260.06 sdetails
#270.06 sdetails
#280.06 sdetails
#290.06 sdetails
#300.06 sdetails
#310.06 sdetails
#320.06 sdetails
#330.06 sdetails
#340.06 sdetails
#350.06 sdetails
#360.06 sdetails
#370.08 sdetails
#380.07 sdetails
#390.08 sdetails
#400.08 sdetails

Code

#include <complex>
typedef long long C;
typedef std::complex<C> Point;
#define X real()
#define Y imag() 

#include <iostream>
#include <vector>
#include <algorithm>

int count_intersections(C y1, C y2, std::vector<C> &horizontal_ys) {
    int count = 0;
    for (auto y3 : horizontal_ys) {
        if (y1 <= y3 && y3 <= y2) count++;
    }
    return count;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<std::pair<std::pair<C, C>, int>> horizontal_lines;
    std::vector<std::pair<C, std::pair<C, C>>> vertical_lines;
    for (int i = 0; i < n; ++i) {
        C x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2) {
            vertical_lines.push_back({x1, {std::min(y1, y2), std::max(y1, y2)}});
        } else {
            horizontal_lines.push_back({{std::min(x1, x2), y1}, 0});
            horizontal_lines.push_back({{std::max(x1, x2), y1}, 1});
        }
    }
    std::sort(horizontal_lines.begin(), horizontal_lines.end());
    std::sort(vertical_lines.begin(), vertical_lines.end());

    auto horizontal_line = horizontal_lines.begin();
    auto vertical_line = vertical_lines.begin();
    std::vector<C> horizontal_ys;
    int count = 0;
    for (C i = -10e6; i <= 10e6; ++i) {
        while (horizontal_line->first.first == i && horizontal_line->second == 0) {
            horizontal_ys.push_back(horizontal_line->first.second);
            horizontal_line++;
        }

        while(vertical_line->first == i) {
            count += count_intersections(vertical_line->second.first, vertical_line->second.second, horizontal_ys);
            vertical_line++;
            if (vertical_line == vertical_lines.end()) {
                std::cout << count << std::endl;
                return 0;
            }
        }

        while (horizontal_line->first.first == i && horizontal_line->second == 1) {
            horizontal_ys.erase(std::remove(horizontal_ys.begin(), horizontal_ys.end(), horizontal_line->first.second), horizontal_ys.end());
            horizontal_line++;
            if (horizontal_line == horizontal_lines.end()) {
                std::cout << count << std::endl;
                return 0;
            }
        }
    }
    std::cout << count << std::endl;
}

Test details

Test 1

Verdict:

input
1
1 1 -1 1

correct output
0

user output
(empty)

Test 2

Verdict:

input
1
-1 1 1 1

correct output
0

user output
(empty)

Test 3

Verdict:

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

correct output
0

user output
(empty)

Test 4

Verdict:

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

correct output
0

user output
(empty)

Test 5

Verdict:

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

correct output
0

user output
(empty)

Test 6

Verdict:

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

correct output
2

user output
1

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

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
(empty)

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
0

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

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
(empty)

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
1

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

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
0

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

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
1

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

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
1

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

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
(empty)

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
2

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

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
0

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

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
3

Feedback: Incorrect character on line 1 col 1: expected "24", got "3"

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
4

Feedback: Incorrect character on line 1 col 1: expected "24", got "4"

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
2

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

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
4

Feedback: Incorrect character on line 1 col 1: expected "24", got "4"

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
4

Feedback: Incorrect character on line 1 col 1: expected "21", got "4"

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
6

Feedback: Incorrect character on line 1 col 1: expected "24", got "6"

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
43

Feedback: Incorrect character on line 1 col 1: expected "576", got "43"

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
56

Feedback: Incorrect character on line 1 col 1: expected "621", got "56"

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
90

Feedback: Incorrect character on line 1 col 1: expected "616", got "90"

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
84

Feedback: Incorrect character on line 1 col 1: expected "624", got "84"

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
83

Feedback: Incorrect character on line 1 col 1: expected "576", got "83"

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
225

Feedback: Incorrect character on line 1 col 2: expected "2464", got "225"

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
345

Feedback: Incorrect character on line 1 col 1: expected "2475", got "345"

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
117

Feedback: Incorrect character on line 1 col 1: expected "2500", got "117"

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
126

Feedback: Incorrect character on line 1 col 1: expected "2464", got "126"

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
214

Feedback: Incorrect character on line 1 col 2: expected "2491", got "214"

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
235

Feedback: Incorrect character on line 1 col 1: expected "9984", got "235"

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
790

Feedback: Incorrect character on line 1 col 1: expected "9919", got "790"

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
1324

Feedback: Incorrect character on line 1 col 1: expected "9991", got "1324"

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
731

Feedback: Incorrect character on line 1 col 1: expected "9999", got "731"

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
248615

Feedback: Incorrect character on line 1 col 3: expected "24992431", got "248615"

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
196277

Feedback: Incorrect character on line 1 col 1: expected "24999775", got "196277"

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
421872

Feedback: Incorrect character on line 1 col 1: expected "24999856", got "421872"

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
477997

Feedback: Incorrect character on line 1 col 1: expected "24999996", got "477997"