블로그 이사 중입니다 >> gumgood.github.io

[BOJ] 2185 직사각형의 합집합 본문

Problem Solving/문제 풀이

[BOJ] 2185 직사각형의 합집합

gumgood 2020. 1. 7. 11:52

가로변, 세로변을 분리시켜서 생각하면 편하다.

세로 변의 길이의 합를 구하는 함수가 있으면 직사각형들을 y=x 축에 대칭시켜 같은 함수로 가로 변의 길이의 합도 구할 수 있다.

 

세로 변의 길이의 합를 구하는 함수를 생각해 보자.

Plane sweeping 방법과 비슷하게 진행하는데 직사각형을 추가하거나 삭제하면서 생기는 변의 길이를 센다.

직사각형을 추가했는데 segtree의 query가 늘어났다면 해당 길이에 해당하는 직사각형이 생겨 새로운 변이 생긴 것이고

직사각형을 삭제했는데 segtree의 query가 줄어들었다면 그 길이에 해당하는 직사각형이 끝나 새로운 변이 또 생길 것이다.

 

주의해야할 점은 직사각형이 삭제됨과 동시에 추가하는 경우 (즉, 같은 크기의 직사각형이 같은 변을 맞대고 있는 경우)

맞대고 있는 변의 길이까지 세어버릴 수 있다. 이를 방지하기 위해서 먼저 직사각형을 추가해주어야 한다.

 

'Problem Solving > 문제 풀이' 카테고리의 다른 글

[BOJ] 2185 직사각형의 합집합  (0) 2020.01.07
[BOJ] 2622 삼각형만들기  (0) 2019.02.14
14891 톱니바퀴  (0) 2019.01.17
14503 로봇 청소기  (0) 2019.01.17
1153 네 개의 소수  (0) 2019.01.15
3163 떨어지는 개미  (0) 2018.12.26
0 Comments
댓글쓰기 폼