[백준 25308] 방사형 그래프

문제 링크 : 25308번: 방사형 그래프 (acmicpc.net)

25308번: 방사형 그래프

 

완전 탐색 및 수학 문제이다.

능력치 8개가 주어질 때, 블록 다각형이 만들어질 수 있는 모든 경우의 수를 구하는 문제이다.

 

※ 문제 접근 방법

 

① permutation 을 이용하여 만들어질 수 있는 \(8!\) 가지 능력치를 배치한다.

 

② (\(a_{1}\), \(a_{2}\), \(a_{3}\)) 부터 (\(a_{8}\), \(a_{1}\), \(a_{2}\)) 까지 8 개의 삼각형이 전부

      블록 다각형인지 확인한다.

      이때, (\(a_{1}\), \(a_{2}\), \(a_{3}\)) 으로 블록 다각형을 판단하는 방법은 다음과 같다.

 

 

우선, (\(a_{1}\), \(a_{2}\), \(a_{3}\)) 를 위와 같이 \(xy\) 평면에 배치한다.

여기서 알 수 있는 점은 원점 (0, 0) 으로부터 거리가 \(a_{1}\), \(a_{2}\), \(a_{3}\) 씩 떨어진 세 개의 점이 존재한다.

따라서 (\(a_{1}\), \(a_{2}\), \(a_{3}\)) 점들에 대한 \(xy\) 좌표는 다음과 같다.

 

• \(a_{1}\) 의 좌표 : (\(a_{1}\), 0)
• \(a_{2}\) 의 좌표 : (\(a_{2} cos(\frac{\pi }{4})\), \(a_{2} sin(\frac{\pi }{4})\))
• \(a_{3}\) 의 좌표 : (0, \(a_{3}\))

우선 오목 다각형인 경우 다음과 같다.

 

 

\(a_{2}\) 의 점이 \(a_{1}\) 의 점과 \(a_{3}\) 의 점으로 만들어진 직선의 방정식 보다 아래에 존재하는 경우다.

이 경우 내각이 \(\pi\) 를 초과한 경우로 오목 다각형이 된다.

 

블록 다각형인 경우는 다음과 같다.

 

 

\(a_{2}\) 의 점이 \(a_{1}\) 의 점과 \(a_{3}\) 의 점으로 만들어진 직선의 방정식 보다 위에 존재하거나

직선 위에 존재하는 경우다.

이 경우 내각이 \(\pi\) 이하인 경우로 블록 다각형이 된다.

 

따라서 \(y \geq  -\frac{a_{3}}{a_{1}}x + a_{3}\) 의 조건에서 \(a_{2}\) 의 좌표값을 넣어서 만족하는 경우를

전부 카운팅하면 결과가 나타난다.

 

 풀이 코드 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

vector<int> order = { 0, 1, 2, 3, 4, 5, 6, 7 };
int a[8];

void input() {
	for (int i = 0; i < 8; i++) {
		cin >> a[i];
	}
}

bool check_block(int x, int y, int z) {
	double x_d = (double)x;
	double y_d = (double)y * sqrt(2.0) / 2.0;
	double z_d = (double)z;

	if (y_d + (z_d / x_d) * y_d - z_d >= 0)
		return true;
	return false;
}

bool is_block() {
	int x, y, z;

	for (int i = 0; i < 8; i++) {
		x = a[order[i]];
		y = a[order[(i + 1) % 8]];
		z = a[order[(i + 2) % 8]];

		if (!check_block(x, y, z))
			return false;
	}

	return true;
}

void solution() {
	int ans = 0;

	do {
		if (is_block()) ans++;
	} while (next_permutation(order.begin(), order.end()));

	cout << ans;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solution();

	return 0;
}