CSES - Aalto Competitive Programming 2024 - wk10 - Homework - Results
Submission details
Task:Line Intersections
Sender:eyong002
Submission time:2024-11-11 01:18:44 +0200
Language:C++ (C++20)
Status:COMPILE ERROR

Compiler report

output/ccctEHN4.o: in function `hv_intersection()':
code.cpp:(.text+0x204): relocation truncated to fit: R_X86_64_PC32 against symbol `e' defined in .bss section in output/ccctEHN4.o
code.cpp:(.text+0x24d): relocation truncated to fit: R_X86_64_PC32 against symbol `e' defined in .bss section in output/ccctEHN4.o
output/ccctEHN4.o: in function `main':
code.cpp:(.text.startup+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in output/ccctEHN4.o
code.cpp:(.text.startup+0x3d): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in output/ccctEHN4.o
code.cpp:(.text.startup+0x93): relocation truncated to fit: R_X86_64_PC32 against symbol `e' defined in .bss section in output/ccctEHN4.o
code.cpp:(.text.startup+0xb1): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in output/ccctEHN4.o
code.cpp:(.text.startup+0xbe): relocation truncated to fit: R_X86_64_PC32 against symbol `e' def...

Code

#include <bits/stdc++.h>
using namespace std;

#define x second
#define y first
const int MAX = 1e9;
typedef pair<int, int> point;

struct event {
    point p1, p2;
    int type;
    event() {};
    event(point p1, point p2, int type) : p1(p1), p2(p2), type(type) {};
};

int n, e = 0;
event events[MAX];
bool compare(event a, event b) {
    return a.p1.x < b.p1.x;
}

set<point> s;

int hv_intersection() {
    int count = 0;
    for (int i = 0; i < e; ++i) {
        event c = events[i];
        if (c.type == 1) {
            s.insert(c.p1);
        }
        else if (c.type == 2) {
            s.erase(c.p2);
        }
        else if (c.type == 3) {
            for (auto it = s.lower_bound(make_pair(c.p1.y, -1)); it != s.end() && it->y <= c.p2.y; ++it) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    cin >> n;
    int p1x, p1y, p2x, p2y;

    for (int i = 0; i < n; ++i) {
        cin >> p1x >> p1y >> p2x >> p2y;
        if (p1x == p2x) {
            events[e++] = event(make_pair(min(p1y, p2y), p1x), make_pair(max(p1y, p2y), p2x), 3);
        } else {
            events[e++] = event(make_pair(min(p1y, p2y), p1x), make_pair(max(p1y, p2y), p2x), 1);
            events[e++] = event(make_pair(max(p1y, p2y), p2x), make_pair(min(p1y, p2y), p1x), 2);
        }
    }

    sort(events, events + e, compare);

    cout << hv_intersection();

    return 0;
}