만드는 중입니다

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

벽록의 가면 (Hard)

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

요약
세 점이 일직선에 놓이지 않는 N개의 점 중에서 네 점을 골라 볼록 사각형을 만들 수 있는 경우의 수를 구합니다.
난이도

보통10점 중 7점

유형
기하, 정렬, 조합론
정답자
아직 제출이 없습니다

문제

마을 뒤편의 큰 산에 도깨비가 한 마리 살고 있다. 도깨비는 가면으로 무서운 얼굴을 가리고 마을 축제에 놀러 가곤 한다. 올해도 축제를 즐긴 도깨비는 다음 축제를 위해 소중한 가면들을 숨겨두려 한다. 가면은 총 44개이며, 산에 있는 NN개의 굴 중 서로 다른 네 곳에 숨길 것이다.

굴의 위치는 좌표평면 위의 점으로 나타낼 수 있다. 기하학을 좋아하는 도깨비는 가면을 숨긴 44개의 굴을 적절한 순서로 이으면 볼록한 사각형이 되도록 할 것이다. 이 문제에서 볼록한 사각형은 4개의 변이 꼭짓점에서만 만나고 내각의 크기가 모두 180° 미만인 사각형을 뜻한다.

호기심이 많은 도깨비는 서로 다른 44개의 굴을 꼭짓점으로 삼아 만들 수 있는 볼록한 사각형이 몇 개인지 궁금해졌다. 굴 NN개의 좌표가 주어질 때 이 개수를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 굴의 개수 NN이 주어진다.

다음 NN개의 줄에 각 굴의 xx좌표와 yy좌표가 공백으로 구분되어 주어진다.

출력

서로 다른 44개의 굴을 꼭짓점으로 삼아 만들 수 있는 볼록한 사각형의 개수를 출력한다.

제한

  • 4≤N≤5004\le N\le 500
  • 주어지는 모든 xx좌표와 yy좌표는 절댓값이 10510^5 이하인 정수이다.
  • 같은 점이 여러 번 주어지지 않는다.
  • 어느 세 점도 한 직선 위에 있지 않다.

예제2

  1. 예제 1

    입력
    5
    0 1
    -2 -2
    -2 2
    2 2
    2 -2
    
    예상 출력
    3
    
  2. 예제 2

    입력
    6
    -8 0
    -4 -7
    -4 7
    4 -7
    4 7
    8 0
    
    예상 출력
    15