[BOJ 10892 // C++] Divide into triangle

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

 

이번에 볼 문제는 백준 10892번 문제인 Divide into triangle이다.
문제는 아래 링크를 확인하자.

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

10892번: Divide into triangle

주어진 3N개의 점을 남김없이 이용해 N개의 서로 영역이 겹치지 않는 삼각형을 구성하는 문제이다.

 

매 순간 남아있는 점들 중 x좌표가 가장 작은 세 점을 구성해 삼각형을 구성하는 전략을 이용하면 문제를 해결할 수 있다. 주어진 어떤 세 점도 한 직선 위에 있는 경우는 없으므로 이렇게 고른 세 점은 항상 삼각형이 됨을 확인하자. 같은 x좌표를 가진 두 점의 경우 어떤 점을 먼저 고르더라도 상관없다.

 

이 삼각형들이 서로 겹치지 않는 이유는 각 삼각형이 존재하는 x좌표의 범위는 다른 삼각형과 많아야 한 점(x값 범위의 경계)에서 겹칠 수 있고, 그 경계에서도 두 삼각형이 겹치는 것은 불가능하기 때문이다. 이해가 잘 안된다면 해당 x좌표를 지나는 y축에 평행한 직선 위에는 점이 많아야 두 개만 있을 수 있고, 각 삼각형에 그 두 점이 나뉘어들어갈 수밖에 없다는 점을 생각해보자.

 

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

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

int N, N3;

pair<pair<int, int>, int> arr[900];

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

	cin >> N; N3 = N * 3;
	for (int i = 0; i < N3; i++) cin >> arr[i].first.first >> arr[i].first.second, arr[i].second = i + 1;

	sort(arr, arr + N3);

	for (int i = 0; i < N3; i += 3) {
		cout << arr[i].second << ' ' << arr[i + 1].second << ' ' << arr[i + 2].second << '\n';
	}
}