백준 25308 (C++) 방사형 그래프

최초 업로드: 2025-04-26 07:57:35

최근 수정 시간: 2025-07-25 09:03:43

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 방사형 그래프

[문제 링크](https://www.acmicpc.net/problem/25308)

## 문제 설명

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

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

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

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

## 입력

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

## 출력

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

## 풀이
#### 볼록 다각형이 되려면, 모든 점에 대해 다음 점이 시계방향 또는 반시계방향으로 한곳에 있어야 한다. 이는 모든 경우의 수(8!)에 대해 CCW 알고리즘을 써서 확인할 수 있다.

``` c++
#include<bits/stdc++.h>
using namespace std;

bool visited[8];
int cnt, permutation[8];
double a[8], pos[8][2];

struct vect {
    double x, y;
};

bool ccw(int a, int b, int c) {
 vect vect1 = {pos[b][0]-pos[a][0], pos[b][1]-pos[a][1]};
 vect vect2 = {pos[c][0]-pos[b][0], pos[c][1]-pos[b][1]};
 return vect1.x*vect2.y - vect2.x*vect1.y <= 0;
}

bool graphChk() {
 for(int i=0;i<8;i++) {
 if(!ccw(i, (i+1)%8, (i+2)%8)) return false;
 }
 return true;
}

void chk(int depth) {
 if(depth==8) {
 pos[0][0] = 0, pos[0][1] = a[permutation[0]];
 pos[1][0] = a[permutation[1]]/sqrt(2), pos[1][1] = a[permutation[1]]/sqrt(2);
 pos[2][0] = a[permutation[2]], pos[2][1] = 0;
 pos[3][0] = a[permutation[3]]/sqrt(2), pos[3][1] = -a[permutation[3]]/sqrt(2);
 pos[4][0] = 0, pos[4][1] = -a[permutation[4]];
 pos[5][0] = -a[permutation[5]]/sqrt(2), pos[5][1] = -a[permutation[5]]/sqrt(2);
 pos[6][0] = -a[permutation[6]], pos[6][1] = 0;
 pos[7][0] = -a[permutation[7]]/sqrt(2), pos[7][1] = a[permutation[7]]/sqrt(2);
 if(graphChk()) cnt++;
 return;
 }
 for(int i=0;i<8;i++) {
 if(!visited[i]) {
 visited[i]=true;
 permutation[depth]=i;
 chk(depth+1);
 visited[i]=false;
 }
 }
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 for(int i=0;i<8;i++) cin >> a[i];
 chk(0);
 cout << cnt;
}
```