[BOJ 25308] 백준 25308번 - 방사형 그래프

		2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 풀이
A		[BOJ 25304] 영수증
B		[BOJ 25305] 커트라인
C		[BOJ 25306] 연속 XOR
D		[BOJ 25307] 시루의 백화점 구경
E		[BOJ 25308] 방사형 그래프

1. 문제

$25308$. 방사형 그래프 (2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 E번)

백준 25308번 - 방사형 그래프 (https://www.acmicpc.net/problem/25308)

2. 풀이

CCW나 Convex Hull 과 같은 어려운 알고리즘을 사용할 필요없이, 모든 순서로 나열한 배열에 대해서 세 점마다 방향성을 확인해주면 된다.

배열의 길이가 $8$이므로 $8!=40320$이어서 브루트포스가 가능하다. 따라서 모든 순서의 배열에 대해 볼록다각형임을 확인한다.

---

세 연속된 점을 기준으로 보면, 다음과 같은 사실을 확인할 수 있다.

모든 $a_{i} (1\leq i\leq 8)$에 대해서 이 조건을 만족하면, 이 다각형을 볼록다각형이라고 부를 수 있다.

이때, $a_{5}$가 기준이 되면, $a_{5}$의 좌표가 $(0,\,-a_{5})$가 되는 것이 아니라 $a_{5}$를 그림의 $a_{1}$ 자리에 놓고 생각하는 것이다. 마찬가지로 $a_{2}$는 $a_{6}$, $a_{3}$는 $a_{7}$이 된다.

3. 채점 결과

4. 회고

이 풀이보다 더 쉬운 풀이가 있을 수도 있는 것 같다.

5. 코드