3108번: LOGO

https://www.acmicpc.net/problem/3108

겹치는 직사각형 쌍마다 간선을 만들고 분리된 그래프의 개수를 센다.

시간복잡도는 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, s1[1001], e1[1001], s2[1001], e2[1001], vis[1001], cnt;
bool out(int a, int b) {
    return s2[a] < s1[b] || e2[a] < e1[b] || s1[b] < s1[a] && s2[a] < s2[b] && e1[b] < e1[a] && e2[a] < e2[b];
}
void dfs(int h) {
    vis[h] = 1;
    for (int i = 0; i <= n; i++) if (!out(h, i) && !out(i, h) && !vis[i]) dfs(i);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", s1 + i, e1 + i, s2 + i, e2 + i);
        if (s1[i] > s2[i]) swap(s1[i], s2[i]);
        if (e1[i] > e2[i]) swap(e1[i], e2[i]);
    }
    for (int i = 0; i <= n; i++) if (!vis[i]) dfs(i), cnt++;
    printf("%d", cnt - 1);
    return 0;
}