Фермер Джон планирует планирует с выгодой продать часть своей земли.
В его собственности находятся \(n\) (\(3 \leq N \leq 300\)) деревьев, каждое
описывается точкой на плоскости, никакие три из которых не коллинеарны.
ФД хочет продать треугольный лот земли, определённый деревьями в своих
вершинах. Имеется \(L = \binom{N}{3}\) таких лотов, которые он может рассмотреть,
перебирая все возможные тройки своих деревьев.
Треугольный лот имеет стоимость \(v\) если он содержит ровно \(v\) деревьев,
внутри себя (деревья в вершинах не считаются, а на границах их и быть не может,
поскольку по условиям все тройки деревьев не коллинеарны). Для каждого $v
в интервале 0 \ldots N-3\(, определите сколько из его \)L$ потенциальных лотов
имеют ценность \(v\).
ФОРМАТ ВВОДА (файл triangles.in):
Первая строка ввода содержит
\(N\).
Каждая из последующих \(N\) строк содержит \(x\) и \(y\) координаты одного дерева -
целые числа в интервале \(0 \ldots 1,000,000\).
ФОРМАТ ВЫВОДА (файл triangles.out):
Выведите \(N-2\) строки, где строка \(i\) содержит количество лотов с ценностью \(i-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 6
17 15
13 15
6 12
9 1
2 7
10 19
|
28
6
1
0
0
|