만드는 중입니다

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

교차하지 않는 선분

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

요약
점 n개가 주어질 때, 다른 어떤 선분과도 교차하지 않는 점 쌍의 선분 개수를 구합니다.
난이도

어려움10점 중 8점

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

문제

평면 위에 점 nn개가 주어진다. 어떤 세 점도 한 직선 위에 있지 않다.

선분 ABAB와 CDCD는 AA, BB, CC, DD와 모두 다른 점 XX를 공유하면 교차한다.

주어진 점 중 두 점을 잇는 모든 선분의 집합을 SS라 하자. SS에 속한 선분 중 SS의 다른 어떤 선분과도 교차하지 않는 선분의 개수를 구하라.

입력

첫째 줄에 점의 개수 nn (3≤n≤10003 \le n \le 1000)이 주어진다.

이어지는 nn개 줄에는 점의 좌표 정수 xix_i와 yiy_i (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9)가 주어진다.

출력

SS의 다른 어떤 선분과도 교차하지 않는 선분의 개수를 출력한다.

예제2

  1. 예제 1

    입력
    4
    1 1
    -1 1
    -1 -1
    1 -1
    
    예상 출력
    4
    
  2. 예제 2

    입력
    4
    -1 -1
    1 -1
    0 1
    0 0
    
    예상 출력
    6