#4741. [Usaco2016 Dec]Lots of Triangles

题目描述

Farmer John is thinking of selling some of his land to earn a bit of extra income. His property cont

ains n trees (3≤N≤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; th

ere are of course L =C(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 tr

ees on the corners do not count, and note that there are no trees on the boundaries since no three t

rees are collinear). For every v = 0 \ldots N-3, please help FJ determine how many of his L potentia

l lots have value v.

农夫约翰打算卖掉一些土地来获得额外的收入。他的土地上有N颗树(3 ≤ N ≤ 300)，可以看做一个平面上的点，

并且没有三点在一条直线上。约翰打算出售一块由三棵树构成的三角形土地，当然这样一共有L =C(n,3)种

可能性。如果一个三角形内部有v个点（不含边界），那么这块土地的价值为v。请帮助约翰统计当v = 0 ... N-3

时，分别有多少块三角形土地价值为v。

输入格式

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.

样例

样例输入

7  

3 6  

17 15  

13 15  

6 12  

9 1  

2 7  

10 19

样例输出

28  

6  

1  

0  

0

数据范围与提示