RiseOJ – 수많은 삼각형

설명

농부 존은 부수입을 얻기 위해 땅의 일부를 팔까 생각 중이다. 그의 사유지에는 $$n$$ 그루의 나무( $3 \leq N \leq 300$ )가 있으며, 각 나무는 2차원 평면의 점으로 표현되고 어떤 세 나무도 한 직선 위에 있지 않다. 존은 나무들을 꼭짓점으로 하는 삼각형 모양의 부지를 파는 것을 고려하고 있다. 사유지의 나무 세 그루의 가능한 모든 조합을 생각하면, 고려할 수 있는 부지는 당연히 $L = \binom{N}{3}$ 개이다.

삼각형 부지의 내부에 정확히 $$v$$ 그루의 나무가 있으면 그 부지의 가치는 $$v$$ 이다(꼭짓점의 나무는 세지 않으며, 어떤 세 나무도 한 직선 위에 있지 않으므로 경계 위에는 나무가 없다는 점에 유의한다). 각 $v = 0 \ldots N-3$ 에 대해, $$L$$ 개의 잠재적 부지 중 가치가 $$v$$ 인 부지가 몇 개인지 구해 존을 도와주자.

문제 출제: 르윈 간(Lewin Gan)

제약

문제 출제: 르윈 간(Lewin Gan)

입력 형식

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

다음 $$N$$ 개의 줄에는 각 나무의 $$x$$ , $$y$$ 좌표가 주어지며, 두 값 모두 $0 \ldots 1,000,000$ 범위의 정수이다.

출력 형식

$$N-2$$ 개의 줄을 출력한다. $$i$$ 번째 줄에는 가치가 $$i-1$$ 인 부지의 개수를 출력한다.

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

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > December > Platinum

올림피아드 > USACO > 2016-2017 > December > Platinum

태그

JudgeUSACO

수많은 삼각형

평가 및 의견

풀이 제출