BOJ 28098 - 폭발 속에서 살아남기
단순히 볼록 껍질을 만들어주고 $(0, 0)$ 이 볼록껍질 안에 접하는게 아닌 완전히 포함되는지 여부로 판별해줄 수 있다.
처음엔 폭발이 일어난 부분으로 $90 \degree$는 못간다는 것으로 정렬해서 스위핑을 해주는 것인줄 알았는데 이건 아니였다.
에디토리얼을 읽어보니 $90 \degree$가 아닌 $180 \degree$까지 완전히 막아버릴 수 있는 것이였다.
✓ 컨벡스 헐 알고리즘을 이용해서도 풀 수 있습니다.
✓ Voronoi diagram 상에서 cell이 unbounded 된다는 것은 문제에서 주어진 N 개의 점과 원점으로 이루어진 N + 1개로부터 구해전 컨벡스 헐 위의 원점 O가 존재한다는것과 동치입니다.
✓ 따라서 컨벡스 헐 알고리즘을 이용해서도 해결할 수 있습니다.
✓ 컨벡스 헐 계산 또한 O(N log N)에 구현할 수 있습니다.
위는 왜 볼록껍질로 풀리는지에 대한 공식 해설이다.
처음엔 단순히 이렇게 $45 \degree$까지만 접하기 때문에 그렇게 막히는 건줄 알았다.
Comments