Quadrants

문제

This problem is about quadrants. What are quadrants? Let us begin with any two perpendicular lines $\mathrm{\ell }\backslash ell$ and ${\mathrm{\ell }}^{\mathrm{\prime }}\backslash ell\; \text{'}$ in the plane ${\mathbb{R}}^2\backslash mathbb\{R\}^2$. If you subtract the two lines $\mathrm{\ell }\backslash ell$ and ${\mathrm{\ell }}^{\mathrm{\prime }}\backslash ell\; \text{'}$ from the whole plane ${\mathbb{R}}^2\backslash mathbb\{R\}^2$, you obtain four connected, unbounded regions. Each of the four regions is called a quadrant. Note that the boundary of a quadrant does not belong to itself.

Now, consider a set $PP$ of points in the plane ${\mathbb{R}}^2\backslash mathbb\{R\}^2$. We are interested in quadrants defined by the set $PP$ of points. Specifically, let $\mathcal{Q}\backslash mathcal\{Q\}$ be the set of quadrants $QQ$ such that the boundary of $QQ$ contains exactly three points of $PP$. Each quadrant Q ∈ \mathcal{Q} is called a $kk$-quadrant if $QQ$ contains exactly $kk$ points of $PP$ in its interior. The figure below shows an example in which the set $PP$ consists of $1414$ points (small circles) and you can see a $55$-quadrant Q ∈ \mathcal{Q} (shaded in cyan), whose boundary contains three points p, q, r ∈ P.

Given a set $PP$ of $nn$ points as input, write a program that computes the number of $kk$-quadrants for every 0 ≤ k ≤ n − 3.

입력

Your program is to read from standard input. The input starts with a line containing a single integer $nn$ (3 ≤ n ≤ 2\,000), where $nn$ is the number of points in the input set $PP$. In each of the following $nn$ lines, given are two integers $xx$ and $yy$, both ranging from −10^6 to ${10}^{6}10^6$, inclusively, that represent the $xx$- and $yy$-coordinates of an input point $(x,y)(x,\; y)$ in $PP$. You may assume that no two input points have the same coordinates, that there are no three points in $PP$ lying in a line, and that there are no two perpendicular lines $\mathrm{\ell }\backslash ell$ and ${\mathrm{\ell }}^{\mathrm{\prime }}\backslash ell\; \text{'}$ in the plane ${\mathbb{R}}^2\backslash mathbb\{R\}^2$ such that | \ell ∩ P| ≥ 2 and |\ell ' ∩ P| ≥ 2.

출력

Your program is to write to standard output. Print exactly n − 2 lines. The $ii$-th line of your output for each 1 ≤ i ≤ n − 2 must contain a single integer that represents the number of (i − 1)-quadrants with respect to the input set $PP$ of $nn$ points.