Square Pasture
Đề bài
Mô tả
Farmer John có con bò trên mặt phẳng tọa độ, con bò thứ đứng tại điểm .
FJ muốn dựng một hàng rào hình vuông có các cạnh song song với hai trục tọa độ. Một con bò được xem là bị bao quanh nếu nó nằm bên trong hoặc nằm trên cạnh của hình vuông.
Vị trí và độ dài cạnh của hình vuông là các số thực tùy ý (không bắt buộc là số nguyên), độ dài cạnh có thể bằng .
Hãy đếm số tập con bò phân biệt mà FJ có thể bao quanh bằng một hàng rào như vậy. Tập rỗng cũng được tính, vì FJ luôn có thể dựng hàng rào ở nơi không có con bò nào.
Dữ liệu vào
- Dòng 1: số nguyên
- dòng tiếp theo: hai số nguyên , , tọa độ của con bò thứ
Dữ liệu ra
Một số nguyên: số tập con bò phân biệt có thể bao quanh.
Ràng buộc
- Tất cả tọa độ phân biệt, tất cả tọa độ phân biệt
- Kết quả nằm trong phạm vi số nguyên có dấu 32 bit
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 0 2 2 3 3 1 1 0 |
14 | Trong tập con, chỉ có hai tập không bao được là và : hình vuông nhỏ nhất chứa hai con bò của mỗi tập đó luôn chứa thêm ít nhất một con bò khác. Vậy đáp án là . |
| 6 1 5 4 1 0 4 5 2 3 0 2 3 |
34 | Ví dụ tập bao được bằng hình vuông : hình vuông này loại được ở dưới và ở trên. Không có hình vuông cạnh với tọa độ nguyên nào bao đúng ba con bò này. |
Bình luận