만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

모래시계 2

시간 제한1.5초메모리 제한1024 MB

요약
세 점이 한 직선 위에 놓이지 않는 N개의 점이 주어질 때, 꼭짓점 하나를 공유하고 서로 겹치지 않는 두 삼각형의 쌍을 셉니다.
난이도

보통10점 중 7점

유형
기하, 정렬, 투 포인터
정답자
아직 제출이 없습니다

문제

모래시계 가공업자 택희의 뒤를 이어 국렬이가 좌표평면 위에 주어진 점들을 받아, 그 안에서 모래시계를 추출하는 작업을 한다.

모래시계는 아래와 같이 생겼다.

[그림] 모래시계

좀 더 정확히 말하면, 다음 조건을 만족하는 것을 모래시계라고 한다.

  1. 한 점을 공유하는 삼각형 2개로 이루어져야 한다.
  2. 두 삼각형은 서로 겹치면 안 된다.

두 모래시계에 속한 정점과 간선의 합집합이 두 모래시계 중 한쪽과 같다면, 두 모래시계는 동일한 모래시계이다. 이 조건을 만족하지 않는 두 모래시계는 모두 서로 다른 모래시계이다.

택희처럼 국렬이도 모래시계의 개수를 빠르게 세고 싶어 한다. 국렬이가 택희에게 도전할 수 있게 도와주자.

입력

N
x1 y1
. . .
xN yN

출력

만들 수 있는 모래시계의 개수를 출력하여라.

제한

  • 1 ≤ N ≤ 1,500. 평면에 있는 점의 개수를 의미한다.
  • −109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9. i번째 점들의 좌표를 의미한다. (1 ≤ i ≤ N)
  • 세 점이 한 직선 위에 있는 경우는 존재하지 않는다.
  • 입력에 주어진 수들은 전부 정수다.

예제1

  1. 예제 1

    입력
    5
    1 2
    -2 1
    -3 -2
    2 -3
    0 0
    
    예상 출력
    6