Vương quốc Mèo
Đề bài
Mô tả
Có thể bạn vẫn còn nhớ bài Kingdom of Kittens trong kỳ thi ICPC Asia Hanoi Regional 2018. Hai năm đã trôi qua, vương quốc ấy đã phát triển thành Vương quốc Mèo, với những bài toán còn khó hơn.
Khi vương quốc lớn dần, những chú mèo cần vạch một đường biên giới mới. Chúng đã tìm được bụi cây đẹp và quyết định dùng các bụi cây này để đánh dấu biên giới.
Không may, mèo không giỏi hình học lắm, nên chúng muốn biên giới là một đa giác có đúng bốn cạnh. Ngoài ra, để tránh nhầm lẫn, với mọi cặp điểm nằm trong đa giác, mọi điểm trên đoạn thẳng nối hai điểm đó cũng phải nằm trong đa giác. Nói cách khác, biên giới phải là một đa giác lồi. Vì kế hoạch vẫn đang được bàn bạc, những chú mèo muốn bạn cho biết có bao nhiêu cách chọn biên giới thỏa mãn mọi yêu cầu của chúng.
Nói một cách chính xác: cho điểm trên mặt phẳng tọa độ, hãy đếm số tứ giác lồi có diện tích dương mà cả đỉnh đều thuộc điểm đã cho.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu có dạng:
- Dòng đầu tiên chứa một số nguyên dương , số điểm ().
- dòng tiếp theo, dòng thứ chứa hai số nguyên và , tọa độ của điểm thứ (). Không có hai điểm nào trùng tọa độ.
Dữ liệu vào kết thúc bằng một dòng chứa số .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng chứa số tứ giác lồi khác nhau thỏa mãn các điều kiện trên.
Ràng buộc
- Tổng của tất cả các bộ dữ liệu không vượt quá .
- , các điểm đôi một phân biệt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 4 1 3 1 2 1 1 1 1 2 1 3 1 4 4 0 0 0 2 2 0 2 2 0 |
9 1 |
Bộ thứ nhất: các điểm nằm trên hai tia vuông góc chung gốc . Một tứ giác lồi phải lấy đúng trong điểm và đúng trong điểm (ba đỉnh thẳng hàng thì không tạo thành tứ giác lồi), nên có cách. Bộ thứ hai: điểm là đỉnh của một hình vuông. |
| 5 0 0 4 0 0 4 1 1 3 3 4 0 0 1 1 2 2 3 3 0 |
2 0 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: hai tứ giác lồi là và . Mọi cách chọn khác hoặc có ba điểm thẳng hàng trên đường , hoặc có nằm trong tam giác . Bộ thứ hai: bốn điểm thẳng hàng. |
Bình luận