[BOJ 28067 // C++] 기하가 너무 좋아

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

 

이번에 볼 문제는 백준 28067번 문제인 기하가 너무 좋아이다.
문제는 아래 링크를 확인하자.

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

28067번: 기하가 너무 좋아

가능한 세 점의 쌍은 순서쌍 $((a,d),(b,e),(c,f))$와 같이 나타낼 수 있다. 각 변수 $a,b,c,d,e,f$는 0 이상 10 이하이므로 이와 같은 모든 순서쌍의 개수는 ${11}^6=1771561$가지이다.

 

각 순서쌍에 대하여 해당 순서쌍이 (1) 삼각형을 나타내는지 확인 후 (2) 해당 삼각형과 대응되는, 즉 합동이면 같은 값을 갖고 그렇지 않다면 다른 값을 갖는 변수를 이용해 개수를 세어 문제를 해결하자.

 

(2)의 판단 기준으로 글쓴이는 변의 길이를 이용한다. 두 삼각형의 세 변의 길이가 같다는 것과 두 삼각형은 합동(SSS합동)임이 동치임은 잘 알려져있다. 이에 따라 두 삼각형의 세 변의 길이'의 제곱'이 같은 것과 두 삼각형이 합동인 것은 동치라고 말할 수 있다. 따라서 위에서 정의한 변수 $a,b,c,d,e,f$를 이용하면 세 변의 길이의 제곱을 간단히 계산할 수 있고, 이들을 크기순으로 나열하면 합동인 두 삼각형은 같은 나열을 갖게 될 것임을 알 수 있다. 이와 같은 나열의 가짓수를 계산해 문제를 해결하자.

 

글쓴이는 해당 나열을 200진법의 정수로 생각(문제 제약조건상 변의 길이의 제곱은 1 이상 200 이하의 값임을 이용)해 해당 나열을 정수에 다시 대응시켜 문제를 해결하였다.

 

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

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

int N, M;
bool visited[8000001];
int cnt;

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

	cin >> N >> M;
	for (int a = 0; a <= N; a++) {
		for (int b = a; b <= N; b++) {
			for (int c = b; c <= N; c++) {
				for (int d = 0; d <= M; d++) {
					for (int e = 0; e <= M; e++) {
						for (int f = 0; f <= M; f++) {
							if ((b - a) * (f - d) == (e - d) * (c - a)) continue; // 삼각형이 아님

							int dx1 = b - a, dx2 = c - b, dx3 = a - c, dy1 = e - d, dy2 = f - e, dy3 = d - f;
							dx1 *= dx1, dx2 *= dx2, dx3 *= dx3, dy1 *= dy1, dy2 *= dy2, dy3 *= dy3;
							int X = dx1 + dy1, Y = dx2 + dy2, Z = dx3 + dy3;
							vector<int> vec = { X - 1,Y - 1,Z - 1 };
							sort(vec.begin(), vec.end());

							int val = vec[0] * 40000 + vec[1] * 200 + vec[2];
							if (visited[val]) continue;
							visited[val] = 1;
							cnt++;
						}
					}
				}
			}
		}
	}

	cout << cnt;
}