CSES - Aalto Competitive Programming 2024 - wk10 - Homework - Results
Submission details
Task:Line Intersections
Sender:arnxxau
Submission time:2024-11-10 17:52:04 +0200
Language:C++ (C++20)
Status:COMPILE ERROR

Compiler report

input/code.cpp:17:5: error: 'Event::Event(int, int, int)' cannot be overloaded with 'Event::Event(int, int, int)'
   17 |     Event(int x, int y1, int y2) : x(x), y1(y1), y2(y2), type(2) {}
      |     ^~~~~
input/code.cpp:14:5: note: previous declaration 'Event::Event(int, int, int)'
   14 |     Event(int x, int y1, int type) : x(x), y1(y1), y2(0), type(type) {}
      |     ^~~~~

Code

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

using namespace std;

struct Event {
    int x;          // x-coordinate of the event
    int y1, y2;     // y-coordinates, y2 is used only for vertical lines
    int type;       // type of event: 0 for start, 1 for end, 2 for query
    
    // Constructor for start and end events
    Event(int x, int y1, int type) : x(x), y1(y1), y2(0), type(type) {}
    
    // Constructor for query events
    Event(int x, int y1, int y2) : x(x), y1(y1), y2(y2), type(2) {}
};

// Comparator for sorting events
bool compareEvents(const Event& a, const Event& b) {
    if (a.x == b.x) {
        return a.type < b.type;
    }
    return a.x < b.x;
}

int main() {
    int n;
    cin >> n;
    vector<Event> events;

    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2) {  // Vertical line
            if (y1 > y2) swap(y1, y2);
            events.emplace_back(x1, y1, y2);
        } else if (y1 == y2) {  // Horizontal line
            if (x1 > x2) swap(x1, x2);
            events.emplace_back(x1, y1, 0);
            events.emplace_back(x2, y1, 1);
        }
    }

    // Sort events
    sort(events.begin(), events.end(), compareEvents);

    // Set to maintain active horizontal segments
    set<int> active;
    int intersectionCount = 0;

    for (auto& event : events) {
        if (event.type == 0) {  // Start of horizontal line
            active.insert(event.y1);
        } else if (event.type == 1) {  // End of horizontal line
            active.erase(event.y1);
        } else if (event.type == 2) {  // Query from a vertical line
            for (auto it = active.lower_bound(event.y1); it != active.end() && *it <= event.y2; ++it) {
                intersectionCount++;
            }
        }
    }

    cout << intersectionCount << endl;
    return 0;
}