문제 링크
- https://icpc.me/15395
사용 알고리즘
- DP
시간복잡도
- $O(N^4)$
풀이
회전 각도에 제한이 있을 때 DP를 하는 것은 꽤 자주 보이는 유형입니다.
모노톤 체인 알고리즘과 비슷한 방식으로 볼록 껍질의 개수를 구할 것입니다. $D1(s, i, j)$를 $s$에서 시작해서 마지막에 $i\rightarrow j$ 변을 사용하는 위 껍질의 개수, $D2(s, i, j)$를 아래 껍질의 개수라고 정의합시다. 점들을 $(x, y)$ 오름차순으로 정렬하면 $O(N^4)$ 시간에 계산할 수 있습니다. 네제곱이지만 상수가 작아서 제한 시간 안에 계산할 수 있습니다.
실제 정답을 구하는 것은 시작점 $s$와 끝점 $j$를 고정한 다음, $\sum D1(s, i, j) \times \sum D2(s, i, j)$를 구하면 됩니다.
전체 코드
1 |
|