# P1715 [USACO16DEC]Lots of Triangles好多三角形

• 39通过
• 102提交
• 题目提供者 FarmerJohn2
• 评测方式 云端评测
• 标签 USACO 2016 高性能
• 难度 省选/NOI-
• 时空限制 1000ms / 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.

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

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$.

一块分出的三角形土地有价值$v$，$v$的大小决定于土地上树的数量，树的数量=土地价值=v （顶点上的树不算，网格图边界不种树）。当$v=0,1...N-3$时，请帮约翰求出有多少三角形地$L$拥有价值$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$.

输入的第一行为树的棵数$N$。

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

输出格式：

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

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

## 输入输出样例

输入样例#1： 复制
7
3 6
17 15
13 15
6 12
9 1
2 7
10 19
输出样例#1： 复制
28
6
1
0
0

## 说明

感谢@Aaronlxz提供翻译

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。