RiseOJ – 삼각형

설명

농부 존은 소들을 위해 삼각형 모양의 목초지를 만들려고 한다.

그의 농장 2차원 지도 위의 서로 다른 점 $(X_1, Y_1) \ldots (X_N, Y_N)$ 에 $$N$$ 개의 울타리 기둥( $3\le N\le 10^5$ )이 있다. 삼각형의 한 변이 $$x$$ 축에 평행하고 다른 한 변이 $$y$$ 축에 평행하기만 하면, 그중 세 개를 골라 삼각형 목초지의 꼭짓점으로 삼을 수 있다.

농부 존이 만들 수 있는 모든 가능한 목초지의 넓이의 합은 얼마인가?

문제 제공: Travis Hance, Nick Wu

제약

배점

테스트 케이스 2는 $$N=200$$ 을 만족한다.
테스트 케이스 3-4는 $N\le 5000$ 을 만족한다.
테스트 케이스 5-10은 추가 제약이 없다.

문제 제공: Travis Hance, Nick Wu

입력 형식

첫째 줄에 $$N$$ 이 주어진다.

다음 $$N$$ 개의 줄 각각에 울타리 기둥의 위치를 나타내는 두 정수 $$X_i$$ 와 $$Y_i$$ 가 주어진다. 각 값은 $-10^4 \ldots 10^4$ 범위(양 끝 포함)이다.

출력 형식

넓이의 합이 정수가 아닐 수 있고 매우 클 수도 있으므로, 넓이의 합의 2배를 $$10^9+7$$ 로 나눈 나머지를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 triangles.in · 출력을 쓸 파일 triangles.out

예제 1

입력

출력

설명

Fence posts $$(0,0)$$ , $$(1,0)$$ , and $$(1,2)$$ give a triangle of area $$1$$ , while
$$(0,0)$$ , $$(1,0)$$ , and $$(0,1)$$ give a triangle of area $$0.5$$ . Thus, the answer is
$2\cdot (1+0.5)=3.$

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > February > Silver

올림피아드 > USACO > 2019-2020 > February > Silver

태그

JudgeUSACO

삼각형

평가 및 의견

풀이 제출