Farmer John đang nghĩ đến việc bán một phần đất để kiếm thêm thu nhập. Khu đất của ông có \(N\) cây (\(3 \leq N \leq 300\)), mỗi cây được biểu diễn bởi một điểm trên mặt phẳng hai chiều và không có ba cây nào thẳng hàng. Farmer John đang cân nhắc bán những lô đất hình tam giác có ba đỉnh là các cây; dĩ nhiên, dựa trên mọi bộ ba cây có thể chọn trong khu đất, có \(L=\binom{N}{3}\) lô như vậy để ông cân nhắc.

Một lô đất hình tam giác có giá trị \(v\) nếu nó chứa đúng \(v\) cây trong phần bên trong (không tính các cây ở ba đỉnh, và lưu ý rằng không có cây nào nằm trên biên vì không có ba cây nào thẳng hàng). Với mỗi \(v=0 \ldots N-3\), hãy giúp Farmer John xác định có bao nhiêu trong số \(L\) lô đất tiềm năng có giá trị \(v\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa tọa độ \(x\), \(y\) của một cây; cả hai tọa độ đều là số nguyên trong khoảng \(0 \ldots 1\,000\,000\).

Dữ liệu ra

In \(N-2\) dòng, trong đó dòng thứ \(i\) chứa số lô đất có giá trị \(i-1\).

Ví dụ

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

28
6
1
0
0

Nguồn

USACO 2016 December Contest, Platinum — Lots of Triangles. Tác giả đề: Lewin Gan.

https://usaco.org/index.php?page=viewproblem2&cpid=672