Parallelogram Counting

• 평면 위의 점들 중 4개를 골라서 만들 수 있는 평행사면형의 개수 세기
• 도형의 개수 세기 / 가장 큰(작은) 도형 찾기 참고. 시간복잡도는 O(n^2)
• 4개의 점이 같은 직선 위에 있는 경우는 없다는 제한이 있어서, 그 경우에 대한 예외처리를 따로 구현해줄 필요가 없어서 코드는 간단하다.

"""Solution code for "BOJ 6744. Parallelogram Counting".

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

Tags: [geometry]
"""

import collections
import itertools
import sys
from teflib import psutils


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

    pair_by_center = collections.Counter(
        (px + qx, py + qy)
        for (px, py), (qx, qy) in itertools.combinations(P, 2)
    )
    answer = sum(c * (c - 1) // 2 for c in pair_by_center.values())

    print(answer)


if __name__ == '__main__':
    main()