Rất nhiều tam giác

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John sở hữu một khu đất có $N$ cây ( $3 \leq N \leq 300$ ) tại các tọa độ nguyên phân biệt trong mặt phẳng 2D. Không có ba cây nào thẳng hàng.

John muốn xem xét tất cả các lô đất hình tam giác mà ba đỉnh là ba cây bất kỳ trong số $N$ cây. Mỗi tam giác có giá trị $v$ bằng số lượng cây nằm hoàn toàn bên trong tam giác đó (không tính ba đỉnh).

Với mỗi giá trị $v$ từ $0$ đến $N - 3$ , hãy đếm số lượng tam giác có đúng $v$ cây bên trong.

Dữ liệu vào

Dòng đầu tiên: số nguyên $N$
$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ là tọa độ của một cây

Dữ liệu ra

In ra $N - 2$ dòng, dòng thứ $i$ (bắt đầu từ $1$ ) chứa số lượng tam giác có đúng $i - 1$ cây bên trong.

Ràng buộc

$3 \leq N \leq 300$
$0 \leq x, y \leq 10^{6}$
Không có ba điểm nào thẳng hàng

Ví dụ

Input	Output	Giải thích
7 3 6 17 15 13 15 6 12 9 1 2 7 10 19	28 6 1 0 0	Có 7 cây, tạo thành $(\binom{7}{3}) = 35$ tam giác. Trong đó 28 tam giác không chứa cây nào bên trong, 6 tam giác chứa đúng 1 cây, và 1 tam giác chứa đúng 2 cây.

Ghi chú

Lưu ý rằng chỉ đếm các cây nằm hoàn toàn bên trong tam giác, không tính các cây nằm trên cạnh hoặc tại đỉnh. Do không có ba điểm thẳng hàng nên không có cây nào nằm trên cạnh tam giác (trừ các đỉnh).

Bình luận

Không có bình luận tại thời điểm này.