[BOJ 2672] 여러 직사각형의 전체 면적 구하기

 

[문제]

 

www.acmicpc.net/problem/2672

2672번: 여러 직사각형의 전체 면적 구하기

 

[필요 개념] 

 

 - 스위핑 (Sweeping)

 

 

[난이도]

 

 - Gold 2 (solved.ac 20.10.29 기준)

 

 

[풀이]

 

N의 크기가 작아서 여러 풀이 방법이 가능하지만, 대체로 이런 유형은 '스위핑'으로 풀리는 경우가 많다. 

우선, 주어지는 입력이 조금 특이한데 알고 보면 크게 다르지 않다. 

 

각 사각형의 왼쪽 아래 꼭짓점의 좌표와 사각형의 폭, 높이가 소수로 주어진다. 

이때, 최대 소수점이하 한 자리까지 주어지고, 1000.0보다 작거나 같은 양의 실수이기 때문에 각 입력에 10을 곱해서 10000 이하의 양의 정수로 생각해도 무방하다. 

그 후, 최종 답을 구할 때에는 넓이이므로 $10^2$를 나눠주면 된다. 

 

각 사각형의 넓이는 (오른쪽 변의 x좌표 - 왼쪽 변의 x좌표)*높이이다.

여기서 문제점은 사각형이 겹치는 부분인데, 직접 겹치는 부분을 모두 제거하는 방식을 이용한다면 매우 까다롭다. 

따라서, 스위핑 기법을 이용한다.

 

현재 x좌표를 a라고 한다면, a ~ a+k의 구간에 어느 사각형이 포함되어 있는지를 확인한다. 

그 후, 이 사각형들이 덮고 있는 y의 구간들을 찾아 구간의 길이*k 만큼 더해준다. 

 

사각형들이 덮고 있는 y의 구간들은 새로운 사각형이 추가되거나, 기존의 사각형이 끝나는 경우에 변화되므로 

각 사각형의 세로 변의 x좌표마다 확인해주면 된다.

 

문제의 그림을 예시로 들어보자. 

 

이처럼 x좌표를 왼쪽에서 오른쪽으로 탐색해가면서 사각형의 넓이를 더해간다. 

 

그 과정에서 중간에 새로운 사각형을 만나서, 포함되는 y의 구간이 추가된다면 이를 갱신해준다. 

 

 

[소스 코드]

 

#include<bits/stdc++.h>

#define all(v) v.begin(), v.end()
#define FOR(i, j, k) for(int i = j; i<=k; i++)
using namespace std;

using ll = long long;

struct sero {
	int x;
	int y1, y2;
	int chk;
	bool operator < (sero b) {
		if (x == b.x) {
			return chk < b.chk;
		}
		else return x < b.x;
	}
};
int A[20001];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int N; cin >> N;
	vector<sero> v;
	FOR(i, 1, N) {
		double a, b, c, d; cin >> a >> b >> c >> d;
		a *= 10; b *= 10; c *= 10; d *= 10;
		sero s;
		s.x = (int)a;
		s.y1 = (int)b;
		s.y2 = (int)(b + d);
		s.chk = 1;
		v.push_back(s);
		s.x = (int)(a + c);
		s.chk = -1;
		v.push_back(s);
	}
	sort(all(v));
	ll ans = 0;
	int lx = 0;
	for (sero s : v) {
		int cnt = 0;
		FOR(i, 0, 20000) {
			if (A[i] > 0) cnt++;
		}
		ans += cnt*(s.x - lx);
		FOR(i, s.y1+1, s.y2) {
			if(s.chk == 1) A[i]++;
			else A[i]--;
		}
		lx = s.x;
	}	
	if (ans % 100 == 0) cout << ans / 100;
	else {
		cout << fixed;
		cout.precision(2);
		cout << ans / 100.0;
	}
}

 

 

사각형의 왼쪽 변인 경우 chk = 1, 오른쪽 변인 경우를 chk = -1로 설정하여, 왼쪽 변이 들어온 경우에는 포함하는 y 구간만큼 A[i]++ 를 해주고, 오른쪽 변이 들어온 경우에는 A[i]-- 를 해주어 구간에서 제거해준다. 

그리고 제일 마지막으로 탐색한 x좌표를 lx에 저장해 두고, 사각형의 세로 변이 들어올 때마다 넓이를 추가해준다.