[백준/28132] 기백을 안 배운다고? (Python)

Problem : https://www.acmicpc.net/problem/28132

28132번: 기벡을 안배운다고?

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 01:05:15

 

---

 

문제 설명

 

 

민우는 22학번이다. 2022학년도 수능 수학에 선택 과목 제도가 생기면서 선택 과목으로 미적분을 택한 민우는 기하와 벡터 과목의 아름다움을 알지 못했다. 기하와 벡터를 독학으로 통달한 민우는 2023 APC를 통해서라도 기하와 벡터의 아름다움을 설파하고자 한다. 2차원 평면상의 두 벡터 v1 = (x1, y1), v2 = (x2, y2)의 내적(dot product)은 다음과 같이 정의된다.

v1 * v2 = x1x2 + y1y2

 

만약 두 벡터의 내적 값이 0이라면, 2차원 평면상에서 두 벡터는 수직임을 의미한다.
 N개의 2차원 벡터가 주어질 때, 1 <= i < j <= N이면서 두 벡터 vi와 vj가 수직인 순서쌍 (i,j)의 개수를 구하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 N이 주어진다. (1 <= N <= 200000) 

둘째 줄부터 N개 줄에 걸쳐 벡터 vi = (xi, yi)의 xi와 yi가 공백으로 구분되어 주어진다 (-10^9 <= xi, yi <= 10^9)

입력으로 주어지는 모든 값은 정수다.

 

출력

 

1 <= i < j <= N을 만족하는 정수 i와 j에 대하여, 두 벡터 vi와 vj가 서로 수직인 순서쌍 (i, j)의 개수를 출력하시오.

 

입력 예시

 

9
1 2
3 5
3 6
2 -1
-4 2
4 -2
-5 0
-8 -16
0 3

 

출력 예시

 

10

 

 

---

 

풀이

 

벡터 (x, y)가 주어지고, 벡터의 내적의 부호는 길이와 상관 없다. 따라서 벡터를 최소 정수쌍으로 변환하여 취급해도 된다. (x, y의 절댓값의 최대공약수로 x, y를 나눠 주기만 하면 된다)

 

또한 두 벡터가 교차하는지 여부를 살펴보려면, (x, y)의 90도, -90도 회전변환 형태인 (-y, x), (y, -x)를 검사할 필요가 있다. i번째 벡터가 들어왔을 때, 저장된 (-y, x) 및 (y, -x)의 개수가 i번 백터와 수직을 이루므로 이를 더해주면 된다. 즉 좌표값에 대하여 해시를 사용하자(파이썬은 딕셔너리가 있다!)

 

엣지 케이스로, x == y == 0인 경우(0벡터) 역시 고려해야 한다. 이 경우의 수를 z라고 두자. 0벡터와 다른 벡터의 내적은 0이므로 이 역시 고려해야 한다..

• 0벡터와 0벡터가 아닌 집합의 경우의 수 = z * (N - z)
• 0벡터끼리의 집합의 경우의 수 = z * (z - 1) / 2

가 된다.

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
orth_dict = defaultdict(int)
zeros = 0
ans = 0

def gcd(a, b) :
  while b :
    a, b = b, a%b
  return a

for _ in range(N) :
  x, y = map(int, input().split())
  if x == y == 0 :
    zeros += 1
    continue
  if x == 0 :
    y = 1
  elif y == 0 :
    x = 1
  else :
    g = gcd(abs(x), abs(y))
    x, y = x // g, y // g
  ans += orth_dict[(x, y)]
  orth_dict[(-y, x)] += 1
  orth_dict[(y, -x)] += 1

print(ans + zeros * (N-zeros) + (zeros * (zeros-1) // 2))

풀이 완료!