Hình chữ nhật kỳ lạ
Đề bài
Mô tả
Trên mặt phẳng có điểm phân biệt, điểm thứ nằm tại tọa độ .
Xét một vùng chữ nhật đặc biệt được xác định bởi ba đường thẳng: (cạnh trái), (cạnh dưới) và (cạnh phải), với . Cạnh trên của vùng kéo dài vô hạn lên phía trên. Một điểm nằm trong vùng khi và chỉ khi và , trong đó , , có thể là số thực bất kỳ.
Với mỗi vùng như vậy, ta thu được tập các điểm nằm bên trong nó. Hãy đếm số tập khác nhau, không rỗng có thể thu được. Hai tập được coi là khác nhau nếu tồn tại ít nhất một điểm thuộc tập này nhưng không thuộc tập kia.
Dữ liệu vào
- Dòng đầu chứa số nguyên , số điểm trên mặt phẳng.
- dòng tiếp theo, dòng thứ chứa hai số nguyên và , tọa độ của điểm thứ .
Tất cả các điểm đều phân biệt.
Dữ liệu ra
In ra một số nguyên duy nhất: số tập điểm khác nhau, không rỗng có thể thu được.
Ràng buộc
- Các điểm đôi một phân biệt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 1 1 2 1 3 |
3 | Ba điểm cùng nằm trên một cột. Với mỗi có đúng một tập gồm điểm (chọn điểm cao nhất), tổng cộng tập. |
| 3 1 1 2 1 3 1 |
6 | Ba điểm cùng nằm trên một hàng. Số tập gồm điểm lần lượt là , tổng cộng . |
| 4 2 1 2 2 3 1 3 2 |
6 | Có tập một điểm, tập hai điểm và tập bốn điểm: . |
Bình luận