기벡을 안배운다고?

• 기울기가 a/b 인 벡터와 수직인 벡터의 기울기는 -b/a 이다. 그러므로 기울기를 모두 계산하고, 기울기별로 벡터 개수를 딕셔너리에 갖고 있으면, 어떤 벡터와 수직인 벡터의 개수를 O(1)에 구할 수 있다. 이것을 모든 벡터에 대해서 계산하면 O(n)에 구할 수 있다.
• 하지만 효율적인 구현을 위해서는 테크닉이 좀 더 필요하다.
• 기울기 a/b 를 그냥 부동소수점으로 구해서 저장하면 실수 오차가 발생할 수 있다. 분수형 자료형을 쓰거나, 아니면 a/b를 직접 기약분수로 바꾸어서 (분자,분모)의 페어로 저장해야 한다.
  • 직접 기약분수로 바꿔서 저장하는 편이 깔끔하고, 분모가 0일때의 처리도 간단하다. 벡터 (x,y)를 받으면, (x gcd(x,y), y gcd(x,y)) 를 저장하도록 하자. 이렇게 하면 x나 y 둘 중 하나가 0이어도 깔끔하게 처리된다. (x,y)가 (0,0) 인 경우에만 예외 처리를 해주면 된다. 다만 gcd연산에 O(log(m)) (m=max(x,y)) 의 시간이 걸리므로, 이것까지 포함하면 총 O(nlogm)의 시간복잡도가 필요하긴 하다.
  • gcd연산을 쓰지 않으려면, 그냥 a/b 를 이용해서 각도정렬을 한 뒤에, 90도 간격을 두고 이동하는 투포인터나 이분탐색을 이용해서 수직인 벡터를 찾을 수 있기는 하다. 하지만 이 방법은 최소한 정렬이 필요하므로 O(nlogn)의 시간복잡도가 필요하고, 이후 과정도 복잡하다. 구현해보지는 않았지만, 그냥 위의 방법보다 느릴것이라 생각된다.
• 또한 처리해야 할것은 (0,0) 벡터의 경우이다. 문제에서 주어진 조건상 (0,0)벡터는 모든 벡터와 수직을 이룬다. 깔끔하게 처리하기 위해서는 영벡터와 영이 아닌 벡터를 구분해서 세어줄 필요가 있다.
  • 영이 아닌 벡터들간의 수직하는 쌍은 위에서 구한 기울기별 개수 딕셔너리를 이용해서 구한다.
    • (a,b) 와 수직하는 벡터는 (-b,a)와 (b,-a) 이므로 두 가지를 모두 세어서 합해서 구할수 있다. 이 경우에 vi와 vj가 수직일때, (i,j)쌍과 (j,i)쌍으로 두번씩 세어지므로 총합을 2로 나누어야 한다
    • 하지만 그냥 간단하게 (a,b)에 대해서 (-b,a)인 경우만 세어서 합해주면, 모든 수직하는 쌍을 한번씩만 셀수 있다. 2로 나눠줄 필요가 없어진다
  • 영벡터와 영이 아닌 벡터들간의 수직하는 쌍은, {영벡터의 개수} * {영이 아닌 벡터의 개수}로 구하면 된다.
  • 영벡터들 간에 수직하는 쌍의 개수는, 영벡터의 개수가 N개일때, C(n,2)로 구하면 된다.
  • 이 세가지 값을 모두 더한 값이 정답이 된다.
• 총 시간 복잡도는
• 추가적으로, 파이썬에서 개수를 딕셔너리에 저장할때 주의할 점이 있다.
  • 가장 깔끔한 방법은 collections.Counter 를 쓰는 것이다. 이 경우에는 아래에 언급할 문제가 발생하지 않는다.
  • 만약 collections.defaultdict(int) 를 사용할 경우에는 주의가 필요하다. 이 경우에는 (a,b)라는 원소의 개수를 구하기 위해서 count[(a,b)] 를 호출하는 순간, count[(a,b)] = 0 과 같은 항목이 딕셔너리에 추가되어 저장된다. 이것이 반복되면 불필요하게 메모리 사용량이 늘어나서 문제가 될수 있다. count.get(a,b), 0) 과 같은 방식으로 개수를 세어야지 이 문제를 방지할 수 있다.

"""Solution code for "BOJ 28132. 기벡을 안배운다고?".

- Problem link: https://www.acmicpc.net/problem/28132
- Solution link: http://www.teferi.net/ps/problems/boj/28132

Tags: [math]
"""

import collections
import math
import sys


def main():
    N = int(sys.stdin.readline())

    counter = collections.Counter()
    zero_vec_count = 0
    for _ in range(N):
        x, y = [int(x) for x in sys.stdin.readline().split()]
        if x == y == 0:
            zero_vec_count += 1
        else:
            g = math.gcd(x, y)
            counter[x // g, y // g] += 1

    zero_nonzero_pair_count = zero_vec_count * (N - zero_vec_count)
    zero_pair_count = zero_vec_count * (zero_vec_count - 1) // 2
    nonzero_pair_count = sum(
        count * counter[y, -x] for (x, y), count in counter.items()
    )

    answer = zero_nonzero_pair_count + zero_pair_count + nonzero_pair_count

    print(answer)


if __name__ == '__main__':
    main()