문제 링크
- http://icpc.me/13329
문제 출처
- 2016 인예 E번
사용 알고리즘
- 컨벡스헐
풀이
먼저, convex hull의 아래 껍질만 고려해도 됩니다.
아래 껍질만 다 따준 다음, 모든 점들을 모아 각도 정렬을 해서 쭉 훑어줄겁니다.
가장 앞에 보이는 다각형이 어떤 것인지를 구할 수 있다면 문제를 해결할 수 있습니다.
각도 순으로 정렬했을 때, 어떤 다각형이 처음 등장하는 점과 마지막으로 등장하는 점이 있습니다.
위 그림과 같은 경우에는, 각 다각형이 빨간 점에서 처음 등장하고 파란 점에서 마지막으로 등장합니다.
set의 비교 기준을 잘 잡아서 어떤 다각형이 앞에 있는지 판단해줄 수 있다면, 빨간 점을 보는 시점에 해당 다각형을 set에 넣어주고, 파란 점을 보는 시점에 해당 다각형을 set에서 빼주면 됩니다.