[BOJ 20157 // C++] 화살을 쏘자!

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

 

이번에 볼 문제는 백준 20157번 문제인 화살을 쏘자!이다.
문제는 아래 링크를 확인하자.

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

20157번: 화살을 쏘자!

 

어떤 한 화살에 두 풍선이 같이 터진다면 원점과 각 풍선을 잇는 두 직선이 동일한 직선이 된다는 성질을 관찰하자. 역은 성립하지 않는데, 화살의 움직임은 직선이 아닌 반직선과 같기 때문이다. 즉 원점을 기준으로 정반대에 있는 두 풍선은 한 화살로 터트릴 수 없다.

 

위의 관찰을 이용하면, 한 화살로 터트릴 수 있는 모든 풍선을 찾는 것은 각 점과 원점을 잇는 직선의 기울기가 같은 점들을 모아 비교하는 것으로 할 수 있다는 것을 발견할 수 있다. 특히, 주어진 각 풍선의 \(x\) 및 \(y\)좌표를 각각 둘의 최대공약수로 나눠 얻을 수 있는 각 좌표의 개수를 센다면 원점을 기준으로 정반대에 있는 점도 자연스럽게 구분해 셀 수 있어 구현을 편하게 할 수 있다.

 

구현 방법에 따라 기울기가 0인(\(x\)축과 평행한) 경우와 무한대인(\(y\)축과 평행한) 직선에 유의해야 할 수도 있으니 참고하자.

 

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

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

int gcd(int x, int y) {
	if (y) return gcd(y, x % y);
	return x;
}

int N;
pair<int, int> P[100000];
int cntinf, cntninf;

pair<int, int> old; int combo;
int ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> P[i].first >> P[i].second;
		if (!P[i].first) {
			if (P[i].second > 0) cntinf++;
			else cntninf++;
			i--, N--;
		}
		else {
			int g = gcd(abs(P[i].first), abs(P[i].second));
			P[i].first /= g, P[i].second /= g;
		}
	}

	sort(P, P + N);
	for (int i = 0; i < N; i++) {
		if (old == P[i]) combo++;
		else {
			ans = max(ans, combo);
			old = P[i], combo = 1;
		}
	}
	ans = max(ans, combo);

	cout << max(ans, max(cntinf, cntninf));
}