아무도 못 푼 문제 - Cube

아무도 못 푼 문제 시간이 돌아왔습니다.

이번에 풀어본 문제는 Cube입니다. 원래는 러시아어로 된 문제인데, 그냥 번역기 돌렸습니다. 참고로 한국어로 번역하면 이게 뭔 소리야 싶은 문장들이 나오는데요. 그때는 영어로 바꾸면 그럭저럭 읽을 만한 내용으로 바꿔줍니다.

가장 단순한 기하학적 구조 중 하나는 정육면체입니다. 밑면의 정점은 시계방향으로 각각 \(A, B, C, D\)로 나타낼 수 있습니다. 윗면의 정점은 또한 각각 \(A_1, B_1, C_1, D_1\)로 나타낼 수 있습니다.

마샤와 파샤는 어떤 조건에서 정육면체의 정점을 양끝으로 하는 두 선분이 교차할지 궁금해졌습니다.

입력으로는 두 줄이 주어집니다. 각 줄은 선분의 양 끝점의 이름을 포함합니다.

두 선분은 서로 다르며, 각 선분의 양 끝점은 다릅니다.

이거 그냥 선분 교차 판정이네, 하고 풀어보려다가 3차원이라는 걸 알아차리고는 좀 뜸을 들여야 했습니다.

이차원 상이라면 그냥 풀어볼만 한데, 괜히 삼차원이 되니 선형 변환이라도 해야하나 하는 생각도 들고 말이죠. 언뜻 생각난 알고리즘은 다음과 같습니다.

두 선분에 겹치는 점이 있는지 확인합니다.
- 있다면 교차합니다. (종료)
- 없다면 2로 진행합니다.
두 선분의 네 끝점이 한 평면 위에 있는지 확인합니다.
- 평면 위에 있다면 3으로 진행합니다.
- 아니라면(꼬여있음) 교차하지 않습니다. (종료)
네 끝 점이 교차하는지 확인합니다. (선형변환 필요?)

0번은 그럭저럭 구현할 수 있겠는데, 기하학은 가물가물해져서 평면의 방정식을 세울 수가 없겠더군요. 세 점을 잡아 평면의 방정식을 세우고 나머지 한 점을 넣어서 0이 나오면 한 평면 위에 있는 건데 말이죠. 요즘 ChatGPT가 유행이던데, 이 녀석한테 물어볼까 하고 그냥 시험삼아 물어봤습니다.

gpt

~~인간 시대의 끝이 도래했다~~

이야… 공부 왜 하나 싶을 정도로 친절하게도 설명해줍디다. 심지어 코드까지 알아서 짜줍니다. 효율성은 잘 몰라도 수식은 적당히 가져오니 잘 돌아갑니다.

struct Vector { 
	int x, y, z;
	Vector operator-(const Vector& r) const { return { x - r.x, y - r.y, z - r.z }; }
	Vector operator*(const Vector& r) const { // 외적
		return {
			y * r.z - z * r.y,
			z * r.x - x * r.z,
			x * r.y - y * r.x
		};
	}
	int magnitude() { return x * x + y * y + z * z; }
} pos[8] = {
	{ 0, 0, 0 }, // A
	{ 0, 0, 1 }, // B
	{ 1, 0, 1 }, // C
	{ 1, 0, 0 }, // D
	{ 0, 1, 0 }, // A1
	{ 0, 1, 1 }, // B1
	{ 1, 1, 1 }, // C1
	{ 1, 1, 0 }  // D1
};

int main() {
	...
	// 네 끝점을 잡습니다.
	Vector p1 = pos[line1[0]];
	Vector p2 = pos[line1[1]];
	Vector p3 = pos[line2[0]];
	Vector p4 = pos[line2[1]];

	// 3개의 점을 가지고 평면의 방정식을 구합니다.
	// 각 선분에 해당하는 벡터를 얻습니다.
	Vector v1 = p2 - p1;
	Vector v2 = p3 - p1;
	// 외적으로 법선벡터를 얻습니다.
	Vector norm = v1 * v2;

	// 법선벡터의 계수 a, b, c를 가지고 절편 d를 얻습니다.
	int d = p1.x * norm.x + p1.y * norm.y + p1.z * norm.z;

	// 네 번째 점을 평면의 방정식에 대입합니다.
	int result = norm.x * p4.x + norm.y * p4.y + norm.z * p4.z - d;
	if (result) { // 방정식의 해가 아니라면
		std::cout << "not on a plane.\n"; // 한 평면 위에 있지 않습니다.
		std::cout << "No\n";
	}
	else {	// 방정식의 해라면
		std::cout << "On the same plane.\n"; // 평면 위에 있습니다.
		...
	}
}

내친김에 선분 교차 판정까지 물어봤는데, 이건 좀 잘못된 답을 내놓습니다. 그냥 두 선분을 외적한 벡터의 크기가 0이 아니면 교차한다고만 하는군요. 그 밑에도 절차를 계속 설명하긴 하지만 처음부터 틀렸기 때문에 그리 정확하진 않겠습니다. 하지만 이 문제에 한해서라면, ChatGPT의 답이 얻어걸리긴 했습니다! 정육면체의 임의의 네 점을 잡아 만든 꼬이지 않은 두 선분은, 반드시 평행하거나 엇갈리거나 둘 중 하나입니다. (단면이 오각형 이상으로 나오는 도형에 대해서는 이 풀이가 먹히지 않습니다.)

굳이 선형 변환 없이도 외적 하나만으로도 풀 수 있게 되었군요.

#include <iostream>

struct Vector { 
	int x, y, z;
	Vector operator-(const Vector& r) const { return { x - r.x, y - r.y, z - r.z }; }
	Vector operator*(const Vector& r) const { // 외적
		return {
			y * r.z - z * r.y,
			z * r.x - x * r.z,
			x * r.y - y * r.x
		};
	}
	int magnitude() { return x * x + y * y + z * z; }
} pos[8] = {
	{ 0, 0, 0 }, // A
	{ 0, 0, 1 }, // B
	{ 1, 0, 1 }, // C
	{ 1, 0, 0 }, // D
	{ 0, 1, 0 }, // A1
	{ 0, 1, 1 }, // B1
	{ 1, 1, 1 }, // C1
	{ 1, 1, 0 }  // D1
};

char s[5];
int line1[2], line2[2];

int main() {
	// 입력 처리
	std::cin >> s;
	for (int i = 0, j = -1; s[i]; ++i) {
		if (s[i] == '1') line1[j] += 4;
		else line1[++j] = s[i] - 'A';
	}
	std::cin >> s;
	for (int i = 0, j = -1; s[i]; ++i) {
		if (s[i] == '1') line2[j] += 4;
		else line2[++j] = s[i] - 'A';
	}

	// 0. 선분이 한 점에서 만나는가?
	if (line1[0] == line2[0] || line1[1] == line2[0] || line1[1] == line2[0] || line1[1] == line2[1]) {
		std::cout << "Yes\n";
	}
	else { // 아니라면
		// get plane
		Vector p1 = pos[line1[0]];
		Vector p2 = pos[line1[1]];
		Vector p3 = pos[line2[0]];
		Vector p4 = pos[line2[1]];

		Vector v1 = p2 - p1;
		Vector v2 = p3 - p1;
		Vector norm = v1 * v2; // 법선 벡터 (평면의 방정식)

		int d = p1.x * norm.x + p1.y * norm.y + p1.z * norm.z;
		int result = norm.x * p4.x + norm.y * p4.y + norm.z * p4.z - d;
		// 1. 네 점이 한 평면 위에 있는가?
		if (result) std::cout << "No\n"; // 꼬인 위치
		else { // 있다면
			v2 = p4 - p3;
			Vector cross = v1 * v2; // 2. 두 선분의 외적의 크기를 구합니다.
			if (cross.magnitude()) std::cout << "Yes\n";
			else std::cout << "No\n";
		}
	}
}

이제 한 명만 푼 문제가 되었습니다.

그나저나 ChatGPT가 뭐 그리 대단한가 했는데, 써보니까 알겠네요. 여러가지 개념을 복합적으로 활용해야 하는 질문에 대해서는 다소 잘못된 답을 내주지만, 하나의 개념에 대해 명료하게 물어보면 정말 무서울 정도로 자세하게 답해줍니다. 한계는 명확하지만 언젠가는 해결될 겁니다. 가만… 이거 치팅인가요?

Categories