acmp 97.cpp

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>

struct Range {
    int a, b;

    Range(int a = 0, int b = 0)
        : a(std::min(a, b))
        , b(std::max(a, b))
    { }

    bool intersect(const Range& other) {
        return !(a > other.b || b < other.a);
    }
};

struct Rectangle {
    int x_min, y_min, x_max, y_max;

    Rectangle(int x1 = 0, int y1 = 0, int x2 = 0, int y2 = 0)
        : x_min(std::min(x1, x2))
        , x_max(std::max(x1, x2))
        , y_min(std::min(y1, y2))
        , y_max(std::max(y1, y2))
    { }

    Rectangle& increase(int r) {
        x_min -= r;
        y_min -= r;
        x_max += r;
        y_max += r;
        return *this;
    }

    static Rectangle read() {
        int x1, y1, x2, y2, r;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &r);
        return Rectangle(x1, y1, x2, y2).increase(r);
    }

    Range rx() const {
        return Range(x_min, x_max);
    }

    Range ry() const {
        return Range(y_min, y_max);
    }

    bool intersect(const Rectangle& other) const {
        return rx().intersect(other.rx()) && ry().intersect(other.ry());
    }
};

int main() {
    freopen("input.txt", "rt", stdin);

    int n;
    scanf("%d", &n);

    std::vector<Rectangle> rect(n);
    for (auto & r : rect) {
        r = Rectangle::read();
    }

    int colors = 0;
    std::vector<int> color(n, -1);

    std::function<void(int)> dfs = [&](int s) {
        for (int i = 0; i < n; ++i) {
            if (i != s && color[i] == -1 && rect[s].intersect(rect[i])) {
                color[i] = colors;
                dfs(i);
            }
        }
    };

    for (int i = 0; i < n; ++i) {
        if (color[i] == -1) {
            dfs(i);
            ++colors;
        }
    }

    printf("%d", colors);

    return 0;
}