[BOJ / C++] 28137 - 뭐라고? 안들려

백준 문제 링크 : 28137 - 뭐라고? 안들려

문제

2차원 좌표 평면상에 현빈이와 수연이가 살고 있다. 현빈이와 수연이는 통화를 자주 하는데, 둘 다 오래된 핸드폰을 쓰기 때문에 통화가 자주 끊긴다. 둘은 이리저리 자리를 옮기며 통화하던 중, 둘의 위치를 잇는 직선의 기울기가
$K$라면 통화가 끊기지 않는다는 사실을 발견했다.

현빈이와 수연이가 있을 수 있는
$N$개의 2차원 좌표가 주어질 때, 통화가 끊기지 않도록 현빈이와 수연이를 배치하는 경우의 수를 구해주자.

입력

첫째 줄에는
$N$과 $K$가 공백으로 구분되어 주어진다.
$(2\leq N\leq 200\,000;$ $-10^{9}\leq K \leq 10^{9})$ 

둘째 줄부터
$N$개 줄에 걸쳐 $i$번 점의 $x$좌표와 $y$좌표가 공백으로 구분되어 주어진다. $(-10^{9}\leq x_{i},y_{i} \leq 10^{9})$ 

같은 좌표는 두 번 이상 입력되지 않으며, 입력으로 주어지는 모든 값은 정수다.

출력

통화가 끊기지 않도록 현빈이와 수연이를 배치하는 경우의 수를 구하여 출력하시오.

입출력 예시

풀이

N이 최대 200,000이므로, O$(N^2)$으로는 시간초과에 당할 수밖에 없습니다. 따라서 어떤 두 점을 비교하여 기울기를 대조하는 방법으로는 풀 수 없습니다. O$(N^2)$보다 더 빠른 어떤 방법을 찾아야 하는데..

따라서, 입력받는 점 $x,y$를 그대로 저장하기보다, 아래와 같은 방법을 사용하기로 합니다.

• 입력받은 점 $(x, y)$가 기울기 $K$를 가질 때의 직선의 방정식을 이용

기울기가 $K$인 임의의 점 $(x, y)$에 대한 직선의 방정식은, 이 직선이 상수 $b$에 대해 $(0, b)$를 지난다고 가정할 때 다음과 같이 쓸 수 있습니다 :
$y = Kx + b$
이를 $b$에 대하여 정리하면,
$b = Kx - y$
"두 점 $(x_1, y_1), (x_2, y_2)$를 잇는 직선의 기울기가 K" 라고 함은 직선의 방정식으로 나타내면 동일한 방정식을 가진다는 뜻이며, 이는 곧 b의 값이 같음을 의미합니다.

따라서, 입력으로 들어온 임의의 점 $(x,y)$에 대해 $b$의 값으로 바꾸어 이것을 key값으로, 해당 key값의 등장 횟수를 value로 하여 map 자료구조에 저장하도록 합니다.

그 후 입력이 끝나면, 각 key들의 value에 대해, 해당 value에서 2자리를 뽑는 경우의 수를 결과에 더해주도록 합니다.
어떤 key값 (위에서 말한 $b$값)에 대한 value를 $v$로 두면, 이 $v$개의 자리 중에서 현빈이와 수연이를 배치하는 경우의 수는

• $vC_2 * 2! = v * (v-1)$

과 같습니다.

이제 문제를 풀 준비가 다 끝났는데, 주의할 점은

• key값을 구할 때, $K * x$ 연산 과정에서 int 범위를 초과할 수 있음
• 결과값인 cnt를 누적할 때 또한 int 범위를 초과할 수 있음

따라서 map의 key와 결과인 cnt는 long long으로 선언합니다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#define INF 2147483647

using namespace std;

map<long long, int>points;

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	int k;
	cin >> n >> k;
	for(int i=0;i<n;i++) {
		int x, y;
		cin >> x >> y;
		points[y-(long long)k*x]++;
	}
	long long cnt = 0;
	for(auto it = points.begin(); it != points.end(); it++) {
		cnt += (long long)(it->second)*(it->second - 1);
	}
	cout << cnt;
}