문제
무한한 크기의 2차원 좌표평면 위에 $N$개의 점이 있다. 점은 $1$번부터 $N$번까지 번호가 붙어 있고, $i$번 점의 좌표는 $(x_i,y_i)$이다. 모든 점의 좌표는 서로 다르다.
$1$ 이상 $N$ 이하의 서로 다른 세 개의 번호 $a$, $b$, $c$를 고른 뒤, 각 번호에 해당하는 점과 점 사이를 선분으로 이으면 삼각형을 만들 수 있다. 이때, 아래 조건을 모두 만족하는 삼각형을 역삼각형이라고 한다.
- $x_a<x_b<x_c$.
- $y_b<y_a$.
- $y_b<y_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(= 10^9 + 7)$로 나눈 나머지를 출력한다. 이 수는 소수이다.
예제 입력 1
6 4 -5 -7 15 6 8 -3 3 0 12 2 -7
예제 출력 1
1154
예제 입력 2
3 -1 -1 0 0 1 1
예제 출력 2
0
출처
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2023. 12. J번
- 문제를 만든 사람: bnb2011
- 문제를 검수한 사람: chogahui05, cologne, hibye1217, kiwiyou, tony9402, utilforever