난이도

Gold 4

인증

문제

게임 캐릭터의 능력치를 한 눈에 보기 좋게 나타내는 방법으로 방사형 그래프가 있다. 캐릭터는 8개의 능력치를 갖고 있고 각 능력치를 $a_1, a_2, \cdots, a_8$이라고 하면, 그래프는 팔각형 형태이고 $k$번째 꼭짓점은 원점을 기준으로 $45\times k$도 방향으로 $a_k$만큼 떨어져 있다.

방사형 그래프를 사용하면 능력치가 얼마나 고르게 분포되어 있는지 쉽게 알 수 있다. 만약 모든 능력치가 동일하다면 정다각형 형태가 되고, 한 능력치가 다른 능력치에 비해 현저히 낮으면 오목 다각형이 된다. 많은 사람들은 방사형 그래프를 볼록 다각형, 즉 모든 내각이 $180°$ 이하인 다각형으로 만들어 자신의 약점을 없애기 위해 노력한다.

시루는 자신의 그래프를 볼록 다각형으로 바꾸고 싶지만, 능력치를 올리는 것은 매우 귀찮기 때문에 한 가지 꼼수를 생각해냈다. 바로 능력치를 나열하는 순서를 바꾸는 것이다. 예를 들어, $\lbrace 6,7,7,8,9,10,11,13 \rbrace$ 순서대로 나열하면 오목 다각형이 되지만, 순서를 바꿔 $\lbrace 7,6,7,8,9,10,11,13 \rbrace$ 순서대로 나열하면 볼록 다각형이 된다.

능력치를 나열하는 순서에 따라 오목 다각형이 될 수도, 볼록 다각형이 될 수도 있기 때문에, 시루는 능력치를 잘 배열해서 볼록 다각형이 되는 경우의 수가 궁금해졌다. 볼록 다각형을 만드는 경우의 수를 구해보자.

입력

첫째 줄에 8개의 능력치를 나타내는 정수 $a_1, a_2, \cdots , a_8$가 공백으로 구분되어 주어진다. ( $1 \leq a_i \leq 10^4$)

출력

8개의 능력치를 잘 배열해서 방사형 그래프를 볼록 다각형으로 만드는 경우의 수를 출력한다.

예제 입력

1 1 1 1 1 1 1 1

예제 출력

40320

해설 및 후기

볼록 및 오목 다각형을 판정하기 위해 역시나 ccw 이론이 사용된다. 각 점을 순회하면서 이전 점과 이후의 점을 얻어내고, 각 점에 대해 좌표를 구한다(각도가 항상 같으므로 편하게 구할 수 있다.) 그 점들을 기준으로 ccw하여 반시계방향이 아닌 시계 방향인지를 체크한다. 만약 그렇다면 이 순열은 볼록 다각형이 아니다.

제출 코드

from math import sin,cos,pi
from itertools import permutations

l = map(int,input().split())
cnt = 0

def ccw(a,b,c):
    res = (b[0]-a[0])*(c[1]-a[1]) - (c[0]-a[0])*(b[1]-a[1])
    if(res < 0):
        return True
    return False

def chk(numLst):
    lstNum = len(numLst)
    for i in range(lstNum):
        a,b,c = numLst[i-1], numLst[i%8], numLst[(i+1)%8]
        a = [0,a]
        b = [b*cos(pi/4),b*sin(pi/4)]
        c = [c,0]
        if(not ccw(a,b,c)):
            return False
    return True

for i in permutations(l,8):
    if(chk(list(i))):
        cnt += 1

print(cnt)