직각 삼각형의 개수

• 점 A를 기준으로, 선분 AB와 선분 AC가 직각을 이룬다면 삼각형 ABC는 직각삼각형이 된다
• 이 원리를 이용하면, 한 점을 고정시킨 후, 그 점을 직각이 되는 꼭짓점으로 하는 직각삼각형을 모두 찾을 수 있다. 고정한 점으로부터 각 점을 잇는 선분들의 기울기를 모두 구한 뒤에, 직각을 이루는 선분 쌍의 개수를 세면 된다. 기벡을 안배운다고? 와 같은 문제가 되고, 같은 방법을 사용해서 O(nlogm) 에 구할 수 있다.
  • 실제로는 중복된 점이 없다는 조건 때문에, 기벡을 안배운다고?에서 신경써야 했던 기울기가 (0,0)인 선분의 처리를 여기에서는 더 간단히 할수 있다. 내 경우는 점 A를 기준으로 할때, 점 A를 포함해 모든 점과의 선분을 다 구하도록 구현했고, 그래서 기울기가 (0,0)으로 표현되는 선분이 딱 한 개 생기게 된다. 그러면 (0,0)에 수직하는 선분의 기울기 역시 (0,0)으로 처리하게 되고, 그래서 수직하는 전체 선분쌍의 개수에는 딱 1개의 잘못된 쌍이 추가되게 된다. 이 값만 빼주면 된다.
• 이것을 모든 점에 대해서 반복하면 O(n^2logm), (m은 좌표값의 최대 범위)에 모든 직각삼각형의 개수를 구할 수 있다. 직각삼각형에서 직각인 점은 유일하므로, 중복으로 세는 경우도 없다. 그냥 단순히 전부 더해주면 끝.

"""Solution code for "BOJ 3008. 직각 삼각형의 개수".

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

Tags: [geometry]
"""

import collections
import math
import sys


def main():
    N = int(sys.stdin.readline())
    P = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    answer = 0
    for px, py in P:
        angle_counter = collections.Counter()
        for qx, qy in P:
            dx, dy = px - qx, py - qy
            g = math.gcd(dx, dy)
            if g > 1:
                dx, dy = dx // g, dy // g
            angle_counter[dx, dy] += 1
        answer += sum(
            count * angle_counter[-dy, dx]
            for (dx, dy), count in angle_counter.items()
        )
    answer -= N

    print(answer)


if __name__ == '__main__':
    main()