BaekJoon 25308번 : 방사형 그래프 (python)

📝 BaekJoon 25308번 : 방사형 그래프 (G4 65.370%)

---

🔎 방사형 그래프 문제

---

📌 아이디어

이전에 풀었던 CCW알고리즘을 이용한 응용 문제이며 모든 직선이 반시계 방향일 때를 판별하는 문제이다.

---

💭 풀이

• 일단 8개의 숫자를 이용하여 나올 수 있는 모든 경우의 수를 permutations를 이용하여 구해주고 주어진 숫자를 좌표로 표현해본다.
• 가운데를 (0,0)으로 생각하고 보면 대각선의 좌표는 k만큼의 길이여야 하기 때문에 (k/sqrt(2),k/sqrt(2))로 표현할 수 있게 된다. 이렇게 각 경우에 대하여 8개 좌표를 부호에 주의해서 표현하고 인접한 좌표 3개를 이용한 직선이 모두 반시계 방향일 때 개수를 count해주는 로직을 통해 볼록 다각형 경우의 수를 셀 수 있게 된다.

---

💻 코드

from itertools import permutations as pm
import sys, math
input = sys.stdin.readline

num = list(map(int,input().split()))
arr = list(pm(num,8))

count = 0
for v in arr :
    x,y = [0]*10, [0]*10
    x[0],y[0] = v[0],0
    x[1],y[1] = v[1]/math.sqrt(2), v[1]/math.sqrt(2)
    x[2],y[2] = 0, v[2]
    x[3],y[3] = -v[3]/math.sqrt(2), v[3]/math.sqrt(2)
    x[4],y[4] = -v[4],0
    x[5],y[5] = -v[5]/math.sqrt(2), -v[5]/math.sqrt(2)
    x[6],y[6] = 0, -v[6]
    x[7],y[7] = v[7]/math.sqrt(2), -v[7]/math.sqrt(2)
    x[8],y[8] = v[0],0
    x[9],y[9] = v[1]/math.sqrt(2), v[1]/math.sqrt(2)

    valid = True
    for i in range(8) :
        fix = (x[i]*y[i+1] + x[i+1]*y[i+2] + x[i+2]*y[i]) - (x[i+1]*y[i] + x[i+2]*y[i+1] + x[i]*y[i+2])
        if fix <= 0 :
            valid = False

    if valid :
        count += 1
print(count)

---