3392 화성지도

 

 

위 이미지와 같이 항상 x축, y축과 평행한 변을 가진 직사각형 들의 면적을 출력하는 문제입니다.

 

 

 

 

예시로 든 이미지를 좌표평면상에 그려보면 위와 같은 그림이 되며, 각 직사각형의 면적에 해당하는 부분에 1을 더하면 오른쪽과 같이 나타납니다.

 

 

1 이상의 값이 들어간 모든 블럭의 값을 합하면 면적이 되는 것을 알 수 있습니다.

 

 

단순하게 직사각형을 모두 탐색한다면 최대 30000의 좌표를 가지기 때문에 30000 * 30000 = 9억 으로 시간이 너무 많이 들게됩니다.

 

 

 

 

 

 

여기서 해결해야하는 부분을 살펴봅시다.

 

1. 직사각형 내부의 숫자를 어떻게 갱신할 것인가.
2. 1이상의 값을 가지는 블럭의 수를 어떻게 세야하는가?

 

크게 두 가지의 문제를 해결해야함을 알 수 있습니다.

 

 

 

 

 

해결법

 

숫자를 갱신하는 조건은 범위내의 면적에 숫자를 갱신해야한다. 입니다.

 

 

 

그리고 이 범위는 x, y 모두 0에서 최대 3만이 되죠.

운이 없으면 이를 모두 탐색하는데에도 n^2의 시간이 걸리게 됩니다.

 

 

 

여기서 특정한 범위내의 값 갱신에 있어서 쓸 수 있는 방법으로 새그먼트 트리를 사용할 수 있습니다.

 

 

 

단말노드에 값을 기록하고, 기록된 값을 부모노드로 올리다보면 루트노드에는 모든 값을 합한 값이 기록될 것 입니다.

그렇게 되면 2번쨰 조건인 1이상의 값을 가지는 블럭의 개수세기도 충족됩니다.

 

 

이제 다시 위의 이미지를 한번 살펴봅시다!

 

 

 

화살표 부분을 살펴보면 x축 기준으로 직사각형이 그려지기 시작하는 부분에는 값이 증가하고, 그리기가 끝나는 부분에서 값이 감소하는 것을 확인할 수 있습니다.

 

 

 

 

 

따라서 x축 기준으로 좌표들을 정렬하고,

직사각형이 시작하는 좌표에는 +1,

직사각형이 끝나는 좌표에는 -1의 값을 준 다음,

세그먼트 트리를 이용하여 값을 갱신하면서,

(현재 x좌표 - 이전의 x좌표) * 세그먼트 트리의 루트값( y크기 )

을 하게되면 전체 면적을 구할 수 있습니다.

 

 

 

세그먼트 트리로 사용할 배열의 크기는 2의 ( log₂n + 2) 승 + 1 ( = 2의 16승 + 1) 로 잡았습니다.

 

#include<iostream>
#include<algorithm>
using namespace std;
#pragma warning(disable:4996);

struct Point {
	// x1 : 현재 x좌표
	// y2 - y1 : y크기
	// value : 시작선 +1, 끝선 -1
	int x, y1, y2, value;
};

Point rect[20001];
int seg[65537], cnt[65537];

bool cmp(Point a, Point b) {
	return a.x < b.x;
}

/*
root = 현재 범위의 루트
start, end = 현재 탐색범위
left, right = 목표 범위
value = 목표범위의 좌표에 더할 값.
*/
void update(int root, int start, int end, int left, int right, int value) {
	if (end < left || right < start) return; // 범위 벗어나면 리턴

	if (left <= start && end <= right) {
		cnt[root] += value;
	}
	else {

		int mid = start + (end - start) / 2;

		// 왼쪽 서브트리
		update(root * 2, start, mid, left, right, value);

		// 오른쪽 서브트리
		update(root * 2 + 1, mid + 1, end, left, right, value);
	}
	if (cnt[root]) seg[root] = end - start + 1;
	else {
		if (start == end)seg[root] = 0;
		else seg[root] = seg[root * 2] + seg[root * 2 + 1];
	}
}

int solve(int size) {
	long long int ret = 0;

	for (int i = 0, xPrev; i < size * 2; i++) {
		Point now = rect[i];

		if (i > 0) {
			//now의 x가 항상 더 크거나 같음 ( 정렬했기때문에 )
			ret += (now.x - xPrev) * seg[1];

		} // 면적 추가하기

		update(1, 0, 32767, now.y1, now.y2, now.value);
		// 새그 업데이트.

		xPrev = now.x;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	for (int i = 0, a, b, c, d; i < n; i++) {
		cin >> a >> b >> c >> d;


		rect[i] = { a,b,d - 1,1 };
		rect[i + n] = { c,b,d - 1,-1 };
	}

	sort(rect, rect + n + n, cmp);

	cout << solve(n);

	return 0;
}

 

 

유사한 문제로 2185 직사각형의 합집합이 있습니다.

2185번: 직사각형의 합집합