만드는 중입니다

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

빈 사각형

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

요약
세 점이 한 직선에 놓이지 않는 점 집합에서 내부에 다른 점이 없는 단순 사각형의 개수를 셉니다. 점은 최대 300개입니다.
난이도

어려움10점 중 8점

유형
기하, 동적 계획법, 정렬, 분할 정복
정답자
아직 제출이 없습니다

문제

사각형은 서로 다른 네 개의 꼭짓점과 서로 다른 네 개의 변을 가진 다각형이며, 변끼리 교차하지 않는다. 이 문제에서는 평면 위의 점 nn개로 이루어진 집합 PP가 주어진다. 어떤 세 점도 한 직선 위에 있지 않다. 꼭짓점이 모두 PP의 점이고, 내부에 PP의 다른 점이 없는 사각형의 개수를 구한다.

예를 들어 PP가 왼쪽 그림과 같이 점 다섯 개로 이루어져 있으면, 꼭짓점이 PP의 점인 서로 다른 사각형은 모두 아홉 개이다. 이 중 내부에 PP의 점을 포함하는 사각형은 오른쪽 그림의 하나뿐이다. 따라서 답은 88이다.

입력

첫째 줄에 PP의 점 개수 nn (1≤n≤3001 \le n \le 300)이 주어진다. 이어지는 nn개의 줄에는 PP의 점 하나씩 좌표를 나타내는 정수 두 개가 주어진다. 모든 좌표는 −109-10^9 이상 10910^9 이하이다. PP의 어떤 세 점도 한 직선 위에 있지 않다.

출력

꼭짓점이 모두 PP의 점이고 내부에 PP의 다른 점이 없는 사각형의 개수를 한 줄에 출력한다.

예제3

  1. 예제 1

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

    입력
    4
    0 0
    10 0
    5 10
    3 2
    
    예상 출력
    3
    
  3. 예제 3

    입력
    10
    10 10
    1 0
    4 8
    -1 -4
    -7 -4
    -3 2
    5 -10
    -10 -5
    1 1
    5 -3
    
    예상 출력
    170