페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3986

Lots of Triangles 1s 128MB

문제

Farmer John is thinking of selling some of his land to earn a bit of extra income. His property contains n trees (3 \leq N \leq 300), each described by a point in the 2D plane, no three of which are collinear. FJ is thinking about selling triangular lots of land defined by having trees at their vertices; there are of course L = \binom{N}{3} such lots he can consider, based on all possible triples of trees on his property.

A triangular lot has value v if it contains exactly v trees in its interior (the trees on the corners do not count, and note that there are no trees on the boundaries since no three trees are collinear). For every v = 0 \ldots N-3, please help FJ determine how many of his L potential lots have value v.

SAMPLE INPUT:

7
3 6
17 15
13 15
6 12
9 1
2 7
10 19

SAMPLE OUTPUT:

28
6
1
0
0

Problem credits: Lewin Gan


입력

The first line of input contains N.

The following N lines contain the x and y coordinates of a single tree; these are both integers in the range 0 \ldots 1,000,000.


출력

Output N-2 lines, where output line i contains a count of the number of lots having value i-1.


출처

USACO 2016 December Platinum

로그인해야 코드를 작성할 수 있어요.