(25308) 방사형 그래프

https://www.acmicpc.net/problem/25308

단계별로 풀어보기

39단계(기하 2) 3번째

 

 

 

모든 경우의 수 8!=40320에 대해 ccw를 돌려 볼록 다각형인지 확인하면 된다.

이때 8개 점의 좌표는 능력치 값 그대로가 아닌 방향에 따른 추가 계산을 해줘야 한다는 점에 주의.

 

 

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int a[8], v[8]= {0, 1, 2, 3, 4, 5, 6, 7}, ans= 0;
  
  for(int i=0;i<8;i++)  cin >> a[i];
  
  auto ccw= [&](){
    long cx[8]= {0, 7071*a[v[1]], 10000*a[v[2]], 7071*a[v[3]], 0, -7071*a[v[5]], -10000*a[v[6]], -7071*a[v[7]]};
    long cy[8]= {10000*a[v[0]], 7071*a[v[1]], 0, -7071*a[v[3]], -10000*a[v[4]], -7071*a[v[5]], 0, 7071*a[v[7]]};
    
    for(int i=0;i<8;i++){
      if((cx[(i+1)%8]-cx[i])*(cy[(i+2)%8]-cy[i])>(cx[(i+2)%8]-cx[i])*(cy[(i+1)%8]-cy[i])){
        return false;
      }
    }
    
    return true;
  };
  
  do{
    ans+= ccw();
  }while(next_permutation(v, v+8));
  
  cout << ans;
  
  return 0;
}