codedoc

plane sweeping - 직사각형 넓이합 구하기 본문

자료구조, 알고리즘 정리

plane sweeping - 직사각형 넓이합 구하기

quince; 2016. 7. 24. 23:47

plane sweeping 사각형 넓이 구하기 알고리즘

문제링크 : https://www.acmicpc.net/problem/3392

 

 




작성중...

 

아래 처럼 직사각형이 겹쳐졌을 때 색칠된 부분의 넓이 합을 구하는 것이 목표입니다.

 





먼저 각 직사각형의 가로선을 포함하는 x축과 평행한 선으로 잘라 줍니다.






필요없는 좌표들을 버리고 나면 다음과 같이 트리를 구성할 수 있습니다.
각 트리는 (y축 합, 카운트)데이터 묶음을 가지고 있고 앞으로 (sum, cnt)라고 부르겠습니다.






각 직사각형의 세로성분 데이터를 얻어오고 각 선들을 x축 기준으로 정렬시킵니다.
이렇게 하면 왼쪽에서부터 sweep을 차례대로 할 수 있을 것입니다.





sweep을 x축이 작은 세로선 부터 시작합니다.
넓이을 어떻게 구하냐면, 각 과정마다 (직사각형에 걸쳐진 파란선 길이 합 * x축 구간)을 더해가며 구할 것 입니다.

오른쪽의 트리는 다음과 같은 방식으로 수정시킵니다.
1. 직사각형의 세로선 데이터를 받아온다.
2. 트리의 세로선에 해당하는 구간의 노드를 구한다.
3. 세로선의 종류에 따라 다음과 같이 작동시킨다.
3-1. 세로선이 시작선일 경우, 해당하는 구간의 노드의 cnt값을 1 증가시킨다.
3-2. 세로선이 끝선을 경우, 해당하는 구간의 노드의 cnt값을 1 감소시킨다.
4. 해당하는 구간의 노드를 포함해 다시 루트노드까지 올라가면서 다음과 같이 작동시킨다.
4-1. 위치한 노드의 cnt값이 0인 경우, 하위 두 자식 노드의 sum값을 더해 위치한 노드의 sum에 저장시킨다.
4-2. 위치한 노드의 cnt값이 0보다 큰 경우, 해당하는 y축 구간 크기를 sum에 저장시킨다.




처음에 찾은 세로선은 시작선(3, 8~12) 입니다.
이 구간에 해당하는 노드(오른쪽에 파란색으로 색칠)를 찾은 뒤 cnt를 증가시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.





다음 세로선은 시작선(6, 1~4) 입니다.
이전에 과정마다 넓이를 계산해서 합한다고 했는데,
현재 세로선과 이전 세로선의 x좌표 차이와 파란선에 걸친 색칠된 부분의 길이 합(루트노드의 sum값)을 곱하면 구할 수 있습니다.
(6-3) * 4 = 12
구간에 해당하는 노드를 찾은 뒤 cnt를 증가시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.






다음 세로선은 시작선(9, 3~10) 입니다.
(9-6) * 7 = 21
구간에 해당하는 노드를 찾은 뒤 cnt를 증가시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.
트리를 보면 겹쳐진 구간을 한 번만 더하게끔 구할 수 있음을 볼 수 있습니다.





다음 세로선은 끝선(13, 8~12) 입니다.
(13-9) * 11 = 44
끝선이므로 구간에 해당하는 노드를 찾은 뒤 cnt를 감소시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.
이때 분명히 cnt값이 0인 경우에만 sum을 수정한다고 했기 때문에 위로 올라가면서 cnt가 1이상인 노드의 sum값은 바뀌지 않습니다.
(즉, 직사각형을 제외해도 해당 노드가 가리키는 구간은 아직도 파란선에 걸쳐져 있다는 뜻)




다음 세로선은 끝선(15, 1~4) 입니다.
(15-13) * 9 = 18
끝선이므로 구간에 해당하는 노드를 찾은 뒤 cnt를 감소시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.






다음 세로선은 시작선(16, 7~14) 입니다.
(16-15) * 7 = 7
시작선이므로 구간에 해당하는 노드를 찾은 뒤 cnt를 증가시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.







다음 세로선은 시작선(17, 7~12) 입니다.
(17-16) * 11 = 11
시작선이므로 구간에 해당하는 노드를 찾은 뒤 cnt를 증가시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.







다음 세로선은 끝선(20, 7~14) 입니다.
(20-17) * 11 = 33
끝선이므로 구간에 해당하는 노드를 찾은 뒤 cnt를 감소시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.








다음 세로선은 끝선(21, 3~10) 입니다.
(21-20) * 9 = 9
끝선이므로 구간에 해당하는 노드를 찾은 뒤 cnt를 감소시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.







다음 세로선은 끝선(23, 7~12) 입니다.
(23-21) * 5 = 10
끝선이므로 구간에 해당하는 노드를 찾은 뒤 cnt를 감소시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.








다음 세로선은 시작선(25, 2~12) 입니다.
(25-23) * 0 = 0
시작선이므로 구간에 해당하는 노드를 찾은 뒤 cnt를 증가시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.







다음 세로선은 끝선(28, 2~12) 입니다.
(28-25) * 10 = 30
끝선이므로 구간에 해당하는 노드를 찾은 뒤 cnt를 감소시키고 다시 루트 노드로 올라가며 sum값을 수정시킵니다.

 

 

앞에서 구했던 넓이들을 나열해 보면

(6-3) * 4 = 12

(9-6) * 7 = 21

(13-9) * 11 = 44

(15-13) * 9 = 18

(16-15) * 7 = 7

(17-16) * 11 = 11

(20-17) * 11 = 33

(21-20) * 9 = 9

(23-21) * 5 = 10

(25-23) * 0 = 0

(28-25) * 10 = 30

총 합은 195로 색칠된 넓이 합은 총 195이다.


<문제>


7728번: Painting patter https://www.acmicpc.net/problem/7728

2185번: 직사각형의 합집합 https://www.acmicpc.net/problem/2185

2601번: 도서실카펫 https://www.acmicpc.net/problem/2601

1 Comments
댓글쓰기 폼