#P1715. [USACO16DEC] Lots of Triangles P
[USACO16DEC] Lots of Triangles P
题目描述
Farmer John is thinking of selling some of his land to earn a bit of extra income. His property contains trees (), 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 such lots he can consider, based on all possible triples of trees on his property.
农民约翰希望通过卖出他拥有的一部分土地来增加收入。他在这片土地上种了棵树(),每棵树都可以用一个二维网格图上的一个坐标来表示,没有三棵树是共线的。约翰想以3棵树做顶点围成三角形来分割地,以确定地的大小和形状,基于约翰所有树可能组成的三树组合,当然有种可能考虑分割贩卖的土地切块。
A triangular lot has value if it contains exactly 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 , please help FJ determine how many of his potential lots have value .
一块分出的三角形土地有价值,的大小决定于土地上树的数量,树的数量=土地价值=v (顶点上的树不算,网格图边界不种树)。当时,请帮约翰求出有多少三角形地拥有价值。
输入格式
The first line of input contains .
The following lines contain the and coordinates of a single tree; these are both integers in the range .
输入的第一行为树的棵数。
接下来的行分别为不同树在二维网格图上的坐标;它们都是介于和之间的的整数;行和列数间用空格隔开。
输出格式
Output lines, where output line contains a count of the number of lots having value .
输出行,其中第行是价值等于的土地块数量。
7
3 6
17 15
13 15
6 12
9 1
2 7
10 19
28
6
1
0
0
提示
感谢@Aaronlxz提供翻译