풀이
사각형을 하나의 노드로 보자.
어떤 두 사각형 a, b가 겹친다면 두 사각형은 연결된 것으로 생각하자.
연결된 사각형들은 연필을 들지 않고 삥삥 돌며 잘 그릴 수 있다.
연필은 연결 요소의 개수 - 1번 들어주면 된다.
단, 시작점인 (0, 0)을 지나는 경우의 예외처리를 잘 해주자.
(x1=0, y1=0, x2=0, y2=0)인 경우도 비교해주면 된다.
Flood fill로 풀어도 된다.
코드
#include <cstdio>
#include <algorithm>
#define y1 fu
using namespace std;
const int n_ = 1000 + 1;
int n, x1[n_], y1[n_], x2[n_], y2[n_], pnt[n_], unq[n_];
int find(int u) {
if (u == pnt[u]) return u;
return pnt[u] = find(pnt[u]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u > v) swap(u, v);
pnt[u] = v;
}
inline bool isout(int i, int j) {
if (x1[i] > x1[j]) swap(i, j);
if (x2[i] < x1[j] || y1[i] > y2[j] || y2[i] < y1[j]) return 1;
if (x1[i] < x1[j] && x2[j] < x2[i] &&
y1[i] < y1[j] && y2[j] < y2[i]) return 1;
return 0;
}
int main() {
int i, j;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
pnt[i] = i;
} pnt[n] = n;
for (i = 0; i < n; i++) for (j = 1; j < n + 1; j++)
if (!isout(i, j)) merge(i, j);
int ans = 0;
for (i = 0; i < n + 1; i++) unq[find(i)] = 1;
for (i = 0; i < n + 1; i++) if (unq[i]) ans++;
printf("%d", ans - 1);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이