문제
농부 창호는 소들을 위해 삼각형 목초지를 만들려고 한다.
N개의 울타리 기둥이 2D 좌표상에 존재하는 상황에서 창호는 3개의 기둥을 선택하여 삼각형 목초지를 만드는데, 한 변이 x축과 평항하며 다른 변은 y축과 평행한 삼각형을 만들려고 한다.
농부 창호가 만들 수 있는 모든 종류의 삼각 목초지 면적의 합을 구하시오.
합이 정수꼴로 나오도록 2배로 출력하고, 너무 클 수 있으니 10^9 + 7 로 나눈 나머지를 출력하시오.
입력
첫 줄에 기둥의 수 N이 주어진다. ( 3 <= N <= 10^5 )
그 다음 N줄에 걸쳐 기둥의 좌표가 주어진다. 좌표는 -10^4 ~ 10^4 까지이며 중복된 위치는 주어지지 않는다.
출력
만들 수 있는 모든 종류의 삼각 목초지 면적의 합의 2배를 출력하고, 너무 클 수 있으니 10^9 + 7 로 나눈 나머지를 출력하시오.
예제1
입력
4
0 0
0 1
1 0
1 2
출력
3
출처
USACO 2020 February Silver