A1932 | $Lots of Triangles P$

来源USACO / 2016

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

农民约翰希望通过卖出他拥有的一部分土地来增加收入。他在这片土地上种了$N$棵树($3\le N\le 300$)，每棵树都可以用一个二维网格图上的一个坐标来表示，没有三棵树是共线的。约翰想以3棵树做顶点围成三角形来分割地，以确定地的大小和形状，基于约翰所有树可能组成的三树组合，当然有$L = \binom{N}{3}$种可能考虑分割贩卖的土地切块。 一块分出的三角形土地有价值$v$，$v$的大小决定于土地上树的数量，树的数量=土地价值=v （顶点上的树不算，网格图边界不种树）。当$v=0,1...N-3$时，请帮约翰求出有多少三角形地$L$拥有价值$v$。

输入的第一行为树的棵数$N$。 接下来的$N$行分别为不同树在二维网格图上的坐标；它们都是介于$0$和$1000000$之间的的整数；行和列数间用空格隔开。

输出$N-2$行，其中第$i$行是价值$v$等于$i-1$的土地块数量。

输入 #1

输出 #1

C++ 编辑器

输入

输出