파일 업로드

🎨AI 리소스 생성

프롬프트 없음

삼각형 공원

profile
실행 시간 제한메모리 제한
1 초512 MB
📃 해결할 문제

수현은 도시 계획가로서 삼각형 모양의 공원을 만들고 싶어합니다.

도시에는 서로 다른 위치 (X1,Y1)(XN,YN)(X_1, Y_1) \ldots (X_N, Y_N)에 총 NN개의 가로등이 있습니다. (3N1053 \le N \le 10^5

수현은 이 가로등 중 세 개를 선택하여 삼각형 모양의 공원을 만들 수 있습니다. 단, 삼각형의 한 변은 가로축(xx축)과 평행하고, 다른 변은 세로축(yy축)과 평행해야만 합니다.

그렇다면, 수현이 만들 수 있는 가능한 모든 공원들의 넓이를 합친 값은 얼마나 될까요?

💻 입력

첫 번째 줄에는 NN이 있습니다.

다음 NN 라인 각각에는 가로등의 위치를 설명하는 범위 104104-10^4 \ldots 10^4 범위 내에서 두 정수 XiX_iYiY_i가 포함되어 있습니다.

🖨️ 출력

면적 합이 반드시 정수일 필요는 없으며 매우 클 수 있기 때문에, 면적 합의 두 배109+710^9+7로 나눈 나머지를 출력합니다.


💻 예제 입력 1
4
0 0
0 1
1 0
1 2
🖨️ 예제 출력 1
3

💡 힌트

가로등 (0,0)(0,0), (1,0)(1,0), 그리고 (1,2)(1,2)는 면적이 11인 삼각형을 만들며, 

(0,0)(0,0), (1,0)(1,0), 그리고 (0,1)(0,1)는 면적이 0.50.5인 삼각형을 만듭니다. 

따라서, 답은 2(1+0.5)=3.2 \cdot (1+0.5)=3.입니다.


출처: USACO 2020 February Contest, Silver Problem 2. Triangles