#PU672. USACO 2016 December Contest, Platinum — Problem 1. Lots of Triangles
USACO 2016 December Contest, Platinum — Problem 1. Lots of Triangles
USACO 2016 December Contest, Platinum — Problem 1. Lots of Triangles
题目描述
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. 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 .
输入格式
The first line of input contains . The following lines contain the and coordinates of a single tree; these are both integers in the range .
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
7
3 6
17 15
13 15
6 12
9 1
2 7
10 19
28
6
1
0
0
Problem credits: Lewin Gan