#PU672. USACO 2016 December Contest, Platinum — Problem 1. Lots of Triangles

    ID: 1240 传统题 文件IO:triangles 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec16来源:usaco.orgscoring:equal_test_cases计算几何枚举

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 nn trees (3≤N≤3003 \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. 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=0…N−3v = 0 \ldots N-3, please help FJ determine how many of his LL potential lots have value 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 0…1,000,0000 \ldots 1,000,000.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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