만드는 중입니다

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

화살표 수집가

시간 제한4초메모리 제한512 MB

요약
점 네 개 (A, B, C, D)로 이루어진 ↖️ 화살표의 개수를 구합니다. C와 D는 A에서 본 각이 B 기준 90도 안에 있고, A와의 거리가 AB보다 짧아야 합니다.
난이도

보통10점 중 7점

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

문제

동현이는 화살표를 모으는 화살표 수집가이다. 요즘 동현이는 매우 신난 상태인데, 얼마 전에 무려 점이 NN개나 있는 화살표 광산을 발견했기 때문이다. NN개의 점은 모두 다르며, 한 직선 위에 세 점이 존재하지 않는다.

화살표 광산에서 화살표를 캐려면 NN개의 점 중 서로 다른 네 점을 골라 이어야 한다. 네 점을 이어 화살표를 만드는 방법은 여러 가지가 있지만, 그중 최상품은 ↖️, 일명 arrow_upper_left이다. ↖️는 아래 조건을 만족하는 서로 다른 네 점의 순서쌍 (A,B,C,D)(A, B, C, D)으로 정의된다.

  • AA의 xx좌표가 BB보다 작고, yy좌표는 BB보다 크다.
  • AA를 중심으로 보았을 때, BB에서 CC가 시계 방향으로 0도 초과 90도 미만에 있다.
  • AA를 중심으로 보았을 때, BB에서 DD가 반시계 방향으로 0도 초과 90도 미만에 있다.
  • 선분 ACAC와 ADAD는 모두 선분 ABAB보다 짧다.

꼼꼼한 동현이는 이 광산에서 캘 수 있는 모든 종류의 ↖️를 다 캐려고 하는데, 그 전에 서로 다른 ↖️가 총 몇 개인지 궁금해졌다. 네 점의 순서쌍이 다르면 다른 ↖️이다. 동현이를 위해 ↖️가 몇 개인지 세어 주자!

입력

첫 번째 줄에 화살표 광산을 이루는 점의 개수 NN이 주어진다.

두 번째 줄부터 NN개의 줄에 걸쳐 각 점의 xx좌표와 yy좌표를 나타내는 두 정수 x_ix\_i, y_iy\_i가 공백으로 구분되어 주어진다.

출력

화살표 광산에 서로 다른 ↖️가 몇 개 있는지 출력한다.

제한

  • 4≤N≤3 0004 \le N \le 3\,000
  • −109≤x_i,y_i≤109-10^9 \le x\_i, y\_i \le 10^9
  • 모든 점의 위치는 서로 다르며, 세 점이 한 직선 위에 있지 않다.

예제1

  1. 예제 1

    입력
    6
    1 6
    3 5
    3 9
    6 7
    7 1
    9 6
    
    예상 출력
    6