Sean :: Dev

Plane Sweeping 직각도형의 넓이를 구할때 쓰이는 알고리즘 곂친 부분이 있기때문에 단순한 공식을 넓이를 구하기 쉽지 않다. 각 직사각형은 4개의 꼭짓점을 가진다. 따라서 n개의 직사각형이라면, 최대 2n개의 x좌표와 2n개의 y좌표가 사용된다. 이렇게 각 꼭짓점으로 나누면, 각 영역의 넓이를 구한뒤 그 합으로 정답을 구할수있다. 먼저 사용되는 x,y좌표를 모두 구한뒤 정렬시킨다. (원소들이 꼭 유일할 필요는 없다) 이후 x,y좌표로 잘려진 영역들을 순회하며, 사각형이 포함되었으면 넓이를 더해준다. 이때, 원소들이 유일하지않다면 정렬될때 같은값이 붙어있으므로 그 영역의 넓이가 0이 되어 무시해도 되게 된다. 이 과정에서 Segment Tree를 사용해 구간갱신속도를 줄여 시간복잡도를 줄일수있다. ..