O(N)으로 순서쌍 찾기1 - 기울기가 K인 직선의 개수

28137번: 뭐라고? 안들려

 

N개의 좌표가 주어질때, A,B를 두개의 좌표에 배치하여 이들을 이은 직선의 기울기가 K인 경우의 수를 찾는다

 

--------------------------------------------------------------------------------------------------------------------------------------------------------------

 

2개의 점을 선택하는 순서쌍을 찾는거니까 단순하게 이중포문을 생각할 수 있지만

 

N <= 20만이라 이중포문으로 O(N^2)에 찾으면 시간초과날 것

 

O(N)에는 찾아야한다는 소리인데...

 

O(N)에 순서쌍을 찾는 문제들은 보통 해시맵(dict)을 쓰는 경우가 많다

 

두 점을 이은 직선의 기울기가 k라는 뜻은?

 

두 점의 좌표 (x1,y1), (x2,y2)라고 하면 (y2-y1)/(x2-x1) = k

 

그러면 (y2 - y1) = k(x2-x1)

 

dict에 어떤 값을 저장해두고, (x,y)를 O(N)에 순회하면 이에 대응하는 다른 점 (x',y')을 찾아야하는데

 

여기서 뭘 저장 해야하지?? 흠...

 

근데 y2 - y1 = kx2 - kx1에서, y2 - kx2 = y1 - kx1으로 양변이 (x1,y1), (x2,y2)에 딱 맞게 정리가 된다

 

즉 두 점 (x1,y1), (x2,y2)에 대하여 이를 이은 직선의 기울기가 k라는 뜻은...

 

각각 y - kx를 계산했을 때 두 값이 같다는 뜻이다.

 

그러므로 dict에 y-kx값을 저장해두고 O(N)에 (x,y)를 순회해서 y-kx값을 해시한다

 

그러면 (x,y)에 대응하는 y-kx의 개수가 c개라면...

 

이 c개중 2개를 선택해서 두 점 A,B를 배치하고, 두 점은 서로 자리를 바꿀 수 있으므로 2!를 곱하면...

 

cC2 * 2! = c(c-1)가지

 

from sys import stdin

n,k = map(int,stdin.readline().split())

H = {}

for _ in range(n):
    
    a,b = map(int,stdin.readline().split())
    H[b-k*a] = H.get(b-k*a,0) + 1

count = 0

for v in H:

    c = H[v]

    count += (c*(c-1))

print(count)