역삼각형

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

요약
x_a<x_b<x_c이고 y_b가 y_a와 y_c보다 작은 모든 세 점에 대해 삼각형 넓이의 두 배를 합한 값을 1,000,000,007로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

유형
정렬, 누적 합, 조합론, 이분 탐색
정답자
아직 제출이 없습니다

문제

무한한 크기의 2차원 좌표평면 위에 NN개의 점이 있다. 점은 11번부터 NN번까지 번호가 붙어 있고, ii번 점의 좌표는 (x_i,y_i)(x\_i,y\_i)이다. 모든 점의 좌표는 서로 다르다.

11 이상 NN 이하의 서로 다른 세 개의 번호 aa, bb, cc를 고른 뒤, 각 번호에 해당하는 점과 점 사이를 선분으로 이으면 삼각형을 만들 수 있다. 이때, 아래 조건을 모두 만족하는 삼각형을 역삼각형이라고 한다.

  • x_a\<x_b\<x_cx\_a\<x\_b\<x\_c.
  • y_b\<y_ay\_b\<y\_a.
  • y_b\<y_cy\_b\<y\_c.

세 점을 선택해서 만들 수 있는 모든 역삼각형 넓이의 합을 SS라고 했을 때, 2S2S를 1,000,000,007(=109+7)1\\,000\\,000\\,007(= 10^9 + 7)로 나눈 나머지를 출력하라. 2S2S는 항상 정수임을 증명할 수 있다.

입력

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

다음 NN개의 줄에 두 정수 x_ix\_i, y_iy\_i가 공백으로 구분되어 주어진다. (−109≤x_i,y_i≤109)(-10^9 \le x\_i, y\_i \le 10^9)

출력

2S2S를 1,000,000,007(=109+7)1\\,000\\,000\\,007(= 10^9 + 7)로 나눈 나머지를 출력한다. 이 수는 소수이다.

예제2

  1. 예제 1

    입력
    6
    4 -5
    -7 15
    6 8
    -3 3
    0 12
    2 -7
    
    예상 출력
    1154
    
  2. 예제 2

    입력
    3
    -1 -1
    0 0
    1 1
    
    예상 출력
    0