[C++] 알고스팟/삼분검색 - 꽃가루 화석

문제 링크

https://algospot.com/judge/problem/read/FOSSIL

algospot.com :: FOSSIL

주어진 두 개의 다각형을 위 껍질과 아래 껍질로 나누어 각 껍질을 삼분검색는 것이 문제의 핵심 알고리즘입니다.

 

삼분검색은 한 개의 지역 극대점이 있는 다음과 같은 그래프를 가지는 유니모달(Unimodal) 함수에서 그래프를 삼등분하며 탐색해나가 지역 극대점을 찾을 수 있습니다.

 

이러한 삼분검색을 문제에 적용하려면 다각형을 반으로 나누어 위와 같은 유니모달 형태로 만들어줘야 합니다. 

문제의 테스트케이스 첫번째 입력값을 나타내면 대략 이런 모습입니다.

도형을 반으로 나눠 위쪽은 upper 아래쪽은 lower로 분류합니다.

 

다음은 두 도형의 겹치는 범위를 찾기 위해 두 도형의 가장 왼쪽에 있는 x좌표 중 큰값과 가장 오른쪽에 있는 x좌표 중 작은 값을 찾고 그 범위를 기준으로 1/3, 2/3 지점을 찾아 삼분탐색해 나갑니다.

이제 중간지점(aab,abb)을 하나씩 살펴보며 어느 선분 사이에 중간지점에 있으면 선분과 중간지점이 교차하는 위치를 구합니다. 이때 upper의 경우 위치들의 최소값을 lower는 위치들의 최대값을 구합니다. 그리고 upper에서 구한 위치에서 lower에서 구한 위치를 빼면 두 다각형이 겹치는 곳에서 중간지점(아래 그래프에서 aab위치)의 높이를 구할 수 있습니다. 이렇게 높이를 삼분검색으로 계속 찾아나가다보면 가장 큰 높이를 구할 수 있습니다.

 

구현 코드