BOJ 12011 - Splitting the field (세그트리)
https://www.acmicpc.net/problem/12011 작년 중순에 동아리에서 소개해줬던 문제. 최대 5만마리의 소들의 좌표가 주어질때, 이 소들을 하나의 펜스에 딱 맞도록 다 들어가도록 할때 그 영억의 넓이 big과 두 영역으로 펜스를 나눠 넣을때 두 영역의 합 small에 대해 big-small의 최소값을 구해라. (좌표 범위 최대 1e9) 한 영역의 크기는 (ymax-ymn)*(xmax-xmn)이다. 펜스가 나눠지는 모양은 다음과 같이 네가지 경우 뿐이다. 1,2번의 경우, x좌표 기준으로 오름차순 정렬한 후 다음과 같이 구할 수 있다. 3,4번의 경우, y좌표 기준으로 오름차순 정렬한 후, 같은 방법으로 구할 수 있다. 구간[l,r] y값 최대, y값 최소, x값 최대, x값 최소를 ..
2020. 2. 7.
