취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25308번 문제인 방사형 그래프이다.
문제는 아래 링크를 확인하자.

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

8가지의 능력치를 배치하는 경우의 수는 총 8!가지가 있다. 이 각 경우의 수를 한번씩 모두 접근해보면서 인접한 세 꼭짓점(8가지)이 이루는 각이 오목한지 볼록한지의 여부를 따져보는 것으로 문제를 해결해보자. 이는 아래와 같이 할 수 있다.

세 인접한 다각형의 꼭짓점을 A, B, C라 하고 각 점들의 원점 O로부터의 거리를 순서대로 각각 x,y,z라 하자.

각 AOC는 직각을 이룬다는 점을 이용하여 OA를 x축 위에, OC를 y축 위에 올려두고 해석기하적인 접근을 통해 방사형 그래프가 볼록다각형을 이룰 조건을 x,y,z로 이루어진 부등식으로 나타내면 x,y,z만을 이용하여 꼭짓점 A, B, C가 이루는 각이 오목한지 볼록한지를 판별할 수 있다.

글쓴이는 위와 같은 좌표평면에서 직선 AC와 기울기가 1인 직선의 교점을 구해 x,y,z로 나타나는 관계식을 유도하였다.

적절한 거듭제곱 및 양변에 적절한 정수를 곱해 실수연산 없이 정수연산만으로 문제를 해결할 수 있다. (사실 x,y,z가 정수인 경우 등호가 성립할 수 없어 실수연산으로도 double형을 이용하면 큰 오차 없이 문제를 해결할 수 있을 것으로 보인다.)

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int ans = 0;
ll arr[8];
bool visited[8];
vector<ll> vec;

bool anglechk(ll& x, ll& y, ll& z) {
	return (x + z) * (x + z) * y * y >= 2 * x * x * z * z;
}

void func(int cnt) {
	if (cnt == 8) {
		if (anglechk(vec[0], vec[1], vec[2]) &&
			anglechk(vec[1], vec[2], vec[3]) &&
			anglechk(vec[2], vec[3], vec[4]) &&
			anglechk(vec[3], vec[4], vec[5]) &&
			anglechk(vec[4], vec[5], vec[6]) &&
			anglechk(vec[5], vec[6], vec[7]) &&
			anglechk(vec[6], vec[7], vec[0]) &&
			anglechk(vec[7], vec[0], vec[1])) ans++;
		return;
	}
	for (int i = 0; i < 8; i++) {
		if (visited[i]) continue;
		visited[i] = 1;
		vec.emplace_back(arr[i]);
		func(cnt + 1);
		vec.pop_back();
		visited[i] = 0;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 8; i++) cin >> arr[i];

	func(0);

	cout << ans;
}