#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
using namespace std;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    double cross(const Point& p) const { return x * p.y - y * p.x; }
};

struct Segment {
    Point a, b;
    int id;
    Segment(Point a, Point b, int id) : a(a), b(b), id(id) {
        if (a.x > b.x) swap(this->a, this->b);
    }
};

struct Event {
    double x;
    int type; // 0: 开始, 1: 结束
    int segId;
    
    bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return type < other.type; // 先处理开始事件
    }
};

class SweepLine {
private:
    vector<Segment> segments;
    vector<Event> events;
    
    double getY(const Segment& seg, double x) {
        if (seg.a.x == seg.b.x) return seg.a.y;
        double t = (x - seg.a.x) / (seg.b.x - seg.a.x);
        return seg.a.y + t * (seg.b.y - seg.a.y);
    }
    
    bool intersect(const Segment& s1, const Segment& s2) {
        Point d1 = s1.b - s1.a;
        Point d2 = s2.b - s2.a;
        Point d3 = s2.a - s1.a;
        
        double cross1 = d1.cross(d2);
        if (abs(cross1) < 1e-9) return false; // 平行
        
        double t1 = d3.cross(d2) / cross1;
        double t2 = d3.cross(d1) / cross1;
        
        return t1 >= 0 && t1 <= 1 && t2 >= 0 && t2 <= 1;
    }
    
public:
    void addSegment(Point a, Point b) {
        segments.push_back(Segment(a, b, segments.size()));
        events.push_back({min(a.x, b.x), 0, (int)segments.size() - 1});
        events.push_back({max(a.x, b.x), 1, (int)segments.size() - 1});
    }
    
    vector<pair<int, int>> findIntersections() {
        sort(events.begin(), events.end());
        
        auto cmp = [&](int a, int b) {
            double x = events.empty() ? 0 : events[0].x;
            return getY(segments[a], x) < getY(segments[b], x);
        };
        
        set<int, decltype(cmp)> active(cmp);
        vector<pair<int, int>> intersections;
        
        for (const Event& e : events) {
            if (e.type == 0) { // 开始事件
                auto it = active.insert(e.segId).first;
                
                // 检查与邻居的相交
                if (it != active.begin()) {
                    auto prev = prev(it);
                    if (intersect(segments[*prev], segments[e.segId])) {
                        intersections.push_back({*prev, e.segId});
                    }
                }
                
                auto next_it = next(it);
                if (next_it != active.end()) {
                    if (intersect(segments[e.segId], segments[*next_it])) {
                        intersections.push_back({e.segId, *next_it});
                    }
                }
            } else { // 结束事件
                auto it = active.find(e.segId);
                
                // 移除后检查邻居是否相交
                if (it != active.begin() && next(it) != active.end()) {
                    auto prev_it = prev(it);
                    auto next_it = next(it);
                    if (intersect(segments[*prev_it], segments[*next_it])) {
                        intersections.push_back({*prev_it, *next_it});
                    }
                }
                
                active.erase(it);
            }
        }
        
        return intersections;
    }
};

int main() {
    SweepLine sweepLine;
    
    // 添加测试线段
    sweepLine.addSegment(Point(0, 0), Point(4, 4));
    sweepLine.addSegment(Point(0, 4), Point(4, 0));
    sweepLine.addSegment(Point(1, 1), Point(3, 3));
    sweepLine.addSegment(Point(2, 0), Point(2, 5));
    
    vector<pair<int, int>> intersections = sweepLine.findIntersections();
    
    cout << "找到 " << intersections.size() << " 个相交：" << endl;
    for (auto& p : intersections) {
        cout << "线段 " << p.first << " 和 " << p.second << " 相交" << endl;
    }
    
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

struct Rectangle {
    int x1, y1, x2, y2;
    Rectangle(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

struct Event {
    int x, y1, y2, type; // type: +1表示左边, -1表示右边
    
    bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return type > other.type; // 先处理+1事件
    }
};

class SegmentTree {
private:
    vector<int> tree, lazy;
    vector<int> coords;
    int n;
    
    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] = (lazy[node] > 0) ? coords[end + 1] - coords[start] : 0;
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
    
    void update(int node, int start, int end, int l, int r, int val) {
        push(node, start, end);
        if (start > r || end < l) return;
        
        if (start >= l && end <= r) {
            lazy[node] += val;
            push(node, start, end);
            return;
        }
        
        int mid = (start + end) / 2;
        update(2 * node, start, mid, l, r, val);
        update(2 * node + 1, mid + 1, end, l, r, val);
        
        push(2 * node, start, mid);
        push(2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
public:
    SegmentTree(vector<int>& coordinates) : coords(coordinates) {
        n = coords.size() - 1;
        tree.resize(4 * n);
        lazy.resize(4 * n);
    }
    
    void update(int l, int r, int val) {
        if (l <= r) update(1, 0, n - 1, l, r, val);
    }
    
    int query() {
        push(1, 0, n - 1);
        return tree[1];
    }
};

long long rectangleUnionArea(vector<Rectangle>& rectangles) {
    vector<Event> events;
    vector<int> yCoords;
    
    // 创建事件并收集y坐标
    for (const Rectangle& rect : rectangles) {
        events.push_back({rect.x1, rect.y1, rect.y2 - 1, 1});
        events.push_back({rect.x2, rect.y1, rect.y2 - 1, -1});
        yCoords.push_back(rect.y1);
        yCoords.push_back(rect.y2);
    }
    
    sort(events.begin(), events.end());
    sort(yCoords.begin(), yCoords.end());
    yCoords.erase(unique(yCoords.begin(), yCoords.end()), yCoords.end());
    
    // 坐标压缩映射
    map<int, int> yMap;
    for (int i = 0; i < yCoords.size(); i++) {
        yMap[yCoords[i]] = i;
    }
    
    SegmentTree segTree(yCoords);
    long long totalArea = 0;
    int prevX = events[0].x;
    
    for (const Event& event : events) {
        // 从上一个x到当前x添加面积
        totalArea += (long long)(event.x - prevX) * segTree.query();
        
        // 更新线段树
        int y1Idx = yMap[event.y1];
        int y2Idx = yMap[event.y2 + 1] - 1;
        segTree.update(y1Idx, y2Idx, event.type);
        
        prevX = event.x;
    }
    
    return totalArea;
}

int main() {
    vector<Rectangle> rectangles = {
        Rectangle(0, 0, 3, 3),
        Rectangle(1, 1, 4, 4),
        Rectangle(2, 2, 5, 5),
        Rectangle(6, 0, 8, 2)
    };
    
    long long area = rectangleUnionArea(rectangles);
    cout << "总并集面积：" << area << endl;
    
    // 验证单个面积
    cout << "单个矩形面积：" << endl;
    for (int i = 0; i < rectangles.size(); i++) {
        Rectangle& r = rectangles[i];
        int area = (r.x2 - r.x1) * (r.y2 - r.y1);
        cout << "矩形 " << i << ": " << area << endl;
    }
    
    return 0;
}