아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

평행사변형 세기

면접 대비

시간 제한1초메모리 제한128 MB

요약
n개의 점이 주어질 때, 같은 중점을 공유하는 점 쌍을 이용해 평행사변형을 이루는 네 점의 조합 수를 센다.
난이도

보통10점 중 6점

유형
해시맵, 기하, 조합론, 수학
정답자
아직 제출이 없습니다

문제

평면 위에 정수 좌표를 가진 서로 다른 점 nn개가 주어진다. 이 점들 중 네 점을 꼭짓점으로 하는 평행사변형의 개수를 구하여라.

정확히 말하면, 네 점에 {A,B,C,D}\{A, B, C, D\}로 이름을 붙였을 때 AB∥CDAB \parallel CD이고 BC∥ADBC \parallel AD가 되도록 만들 수 있는, 크기가 44인 부분집합의 개수를 센다. 주어진 점들 중 어떤 네 점도 한 직선 위에 있지 않다.

입력

첫째 줄에 테스트 케이스의 개수 tt (1≤t≤101 \le t \le 10)가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 정수 nn (1≤n≤10001 \le n \le 1000)이 주어진다. 다음 nn개의 줄에는 각각 한 점의 좌표를 나타내는 두 정수 xx와 yy (∣x∣,∣y∣≤109|x|, |y| \le 10^9)가 공백으로 구분되어 주어진다.

출력

tt개의 줄을 출력한다. ii번째 줄에는 ii번째 테스트 케이스에 대한 평행사변형의 개수를 출력한다.

예제3

  1. 예제 1

    입력
    2
    6
    0 0
    2 0
    4 0
    1 1
    3 1
    5 1
    7
    -2 -1
    8 9
    5 7
    1 1
    4 8
    2 0
    9 8
    
    예상 출력
    5
    6
    
  2. 예제 2

    입력
    1
    4
    0 0
    1 0
    1 1
    0 1
    
    예상 출력
    1
    
  3. 예제 3

    입력
    2
    5
    0 0
    2 0
    0 2
    2 2
    1 1
    4
    0 0
    3 1
    4 4
    1 3
    
    예상 출력
    1
    1