역삼각형

면접 대비

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

요약

N개의 점에서 x좌표 순서상 가운데 점의 y좌표가 세 점 중 가장 작은 모든 역삼각형의 넓이 합을 2배 한 값을 10^9+7로 나눈 나머지를 구합니다.

문제

무한한 크기의 2차원 좌표평면 위에 $N$ 개의 점이 있다. 점에는 $1$ 번부터 $N$ 번까지 번호가 붙어 있고, $i$ 번 점의 좌표는 $(x_i, y_i)$ 이다. 모든 점의 좌표는 서로 다르다.

$1$ 이상 $N$ 이하의 서로 다른 세 번호 $a$ , $b$ , $c$ 를 고르고, 각 번호에 해당하는 점을 선분으로 이으면 삼각형이 된다. 아래 조건을 모두 만족하는 삼각형을 역삼각형이라고 한다.

세 점을 골라 만들 수 있는 모든 역삼각형의 넓이 합을 $S$ 라고 할 때, $2S$ 를 $1,000,000,007$ (= $10^9 + 7$ )로 나눈 나머지를 구하라. $2S$ 는 항상 정수임을 증명할 수 있다.

첫째 줄에 $N$ 이 주어진다. ( $3 \le N \le 300\,000$ )

다음 $N$ 개의 줄에 두 정수 $x_i$ , $y_i$ 가 공백으로 구분되어 주어진다. ( $-10^9 \le x_i, y_i \le 10^9$ )

$2S$ 를 $1,000,000,007$ 로 나눈 나머지를 출력한다. 이 수는 소수이다.