#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 NN trees (3N3003 \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=(N3)L = \binom{N}{3} such lots he can consider, based on all possible triples of trees on his property.

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

A triangular lot has value vv if it contains exactly vv 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=0N3v = 0 \ldots N-3, please help FJ determine how many of his LL potential lots have value vv.

一块分出的三角形土地有价值vvvv的大小决定于土地上树的数量,树的数量=土地价值=v (顶点上的树不算,网格图边界不种树)。当v=0,1...N3v=0,1...N-3时,请帮约翰求出有多少三角形地LL拥有价值vv

输入格式

The first line of input contains NN.

The following NN lines contain the xx and yy coordinates of a single tree; these are both integers in the range 01,000,0000 \ldots 1,000,000.

输入的第一行为树的棵数NN

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

输出格式

Output N2N-2 lines, where output line ii contains a count of the number of lots having value i1i-1.

输出N2N-2行,其中第ii行是价值vv等于i1i-1的土地块数量。

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

提示

感谢@Aaronlxz提供翻译