취미로 코딩하기

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

이번에 볼 문제는 백준 15330번 문제인 Parallel Lines이다.
문제는 아래 링크를 확인하자.

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

\(2N\)개의 점을 짝지어 \(N\)개의 선분을 구성하는 방법의 수는 \((2N-1)\cdot (2N-3)\cdots 5 \cdot 3 \cdot 1\)과 같다. \(N=8\)일 경우 이 값은 2027025로 충분히 작아 완전탐색이 가능함을 알 수 있다.

위 내용을 관찰하는 것은 어렵지 않다. 각 점에 번호를 1부터 \(2N\)까지 부여하자. 결국 모든 점은 선분 구성에 사용되어야하므로, 현재 쌍이 정해지지 않은 가장 작은 번호의 점의 짝을 다른 점을 골라 주는 것을 반복하는 과정을 잘 생각해보면 위의 식을 쉽게 유도할 수 있을 것이다.

이제 가능한 모든 선분 구성에 대하여 평행한 선분의 쌍의 개수를 직접 세고, 그중 최댓값을 구해 문제를 해결하자. 문제 조건에 따라 어떤 세 점도 한 직선 위에 있지 않으므로 이 부분 또한 큰 예외처리 없이 구현할 수 있다. 구현에 따라 축과 평행한 선분이 있을 경우의 판정에 유의해 구현하자.

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

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

int N, NN;
int P[16][2];
int ans;
vector<pair<int, int>> vec;
bool visited[16];

void func(int n) {
	if (n == NN) {
		int cnt = 0;
		for (int i = 0; i < NN; i++) {
			for (int j = i + 1; j < NN; j++) {
				if (!vec[i].second && !vec[j].second) cnt++;
				else if (!vec[i].second || !vec[j].second) continue;
				else if (vec[i].first * vec[j].second == vec[i].second * vec[j].first) cnt++;
			}
		}
		ans = max(ans, cnt);
		return;
	}

	int i = 0;
	while (visited[i]) i++;
	visited[i] = 1;
	for (int j = i + 1; j < N; j++) {
		if (visited[j]) continue;
		vec.emplace_back(make_pair(P[j][1] - P[i][1], P[j][0] - P[i][0]));
		visited[j] = 1;
		func(n + 1);
		visited[j] = 0;
		vec.pop_back();
	}
	visited[i] = 0;
}

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

	cin >> N; NN = N / 2;
	for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];
	func(0);

	cout << ans;
}