algospot 꽃가루 화석 (문제 ID: FOSSIL) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/FOSSIL

algospot.com :: FOSSIL

볼록 다각형을 이루는 점들의 좌표가 반시계 방향으로 각각 두개 주어질때, 두 볼록 다각형이 이루는 교집합 다각형의 세로 길이 최댓값을 구하는 문제이다.

두 볼록 다각형의 교집합 다각형은 볼록 다각형이고 이는 삼분법을 이용하여 x좌표를 탐색하면 정답을 찾을 수 있다는것을 이미한다.

교집합 다각형을 추상화 하는 방법은 일단 각각의 볼록 다각형들의 오목 부분과 볼록부분을 나눠서 두 볼록 다각형 구분없이 저장한다.

그 다음 x좌표에 따른 교집합 다각형의 세로 길이를 구할때마다 x좌표에 해당하는 위로 볼록 부분중 작은 쪽, 오목 부분중 큰 쪽의 y좌표 차이를 확인하면 된다.

이제 x좌표에 따른 교집합 다각형의 세로 길이를 구할 수 있고 삼분법을 이용하면 적절한 답을 추적할 수 있다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/13.%20NumericalAnalysis/RATIO.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1