Lots of Triangles

题目描述

Farmer John 正在考虑出售他的一些土地来赚取一点额外收入。他的土地上有 $n$ 棵树（$3 \leq N \leq 300$），每棵树由二维平面上的一个点描述，且任意三棵树都不共线。FJ 正在考虑出售以树作为顶点所定义的三角形地块；显然，基于他土地上所有可能的三棵树的组合，他可以考虑的地块总数为 $L = \binom{N}{3}$。 如果一个三角形地块的内部恰好包含 $v$ 棵树，则该地块的价值为 $v$（位于三角形顶点的树不计入；并且由于任意三棵树不共线，三角形边界上不会有树）。对于每个 $v = 0 \ldots N-3$，请帮助 FJ 确定在他这 $L$ 个潜在地块中，有多少个地块的价值为 $v$。

输入格式

第一行输入 $N$。 接下来的 $N$ 行每行包含一棵树的 $x$ 和 $y$ 坐标；二者均为整数，范围在 $0 \ldots 1,000,000$ 之间。

输出格式

输出 $N-2$ 行，其中第 $i$ 行输出价值为 $i-1$ 的地块数量。

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

28
6
1
0
0

提示

题目来源：Lewin Gan

标签: USACO|2016|Platinum

来源

USACO|2016|Platinum