Máy bán hàng tự động
Đề bài
Mô tả
Trường đại học cuối cùng đã quyết định lắp đặt những chiếc máy bán hàng tự động được ưa chuộng ở nhiều vị trí chiến lược trong khuôn viên. Thực ra, để bù đắp cho tình trạng thiếu máy trước đây, trường quyết định lắp càng nhiều máy càng tốt.
Đáng ngạc nhiên là khuôn viên sẽ không bị lấp kín bởi máy mới, vì có những quy định pháp lý khá nghiêm ngặt về vị trí đặt máy. Trường đã đánh dấu mọi vị trí có thể đặt máy bán hàng cùng tọa độ của chúng trên bản đồ khuôn viên. Ngoài ra, trường còn phải tuân thủ quy tắc an toàn của nhà sản xuất: khoảng cách giữa hai máy bán hàng bất kỳ phải ít nhất là mét. Hãy giúp trường xác định số máy bán hàng lớn nhất có thể lắp đặt trong khuôn viên.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa số nguyên là số vị trí có thể đặt máy trên bản đồ (). Tiếp theo là dòng mô tả tọa độ các vị trí, mỗi dòng mô tả một vị trí bằng một cặp tọa độ nguyên, tính bằng mét. Các vị trí trong cùng một bộ dữ liệu đôi một khác nhau. Mọi tọa độ đều không âm và không vượt quá .
Đảm bảo rằng mọi vị trí tạo thành một nhóm liên thông duy nhất, tức là có thể bắt đầu từ một vị trí bất kỳ và đi tới mọi vị trí khác bằng một dãy bước, mỗi bước thay đổi đúng một tọa độ đi , mà không rời khỏi khu vực được phép đặt máy.
Dữ liệu vào kết thúc ở cuối tệp.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên là số máy bán hàng lớn nhất có thể lắp đặt trong khuôn viên.
Ràng buộc
- .
- mọi tọa độ , các vị trí trong một bộ dữ liệu đôi một khác nhau.
- Các vị trí của một bộ dữ liệu liên thông theo các bước thay đổi một tọa độ đi .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 0 0 0 1 1 0 1 1 6 0 1 1 0 1 1 1 2 1 3 2 2 |
2 4 |
Bộ thứ nhất là hình vuông : chọn hai góc chéo nhau và , cách nhau mét. Bộ thứ hai chọn được , , và . |
| 1 5 5 3 0 0 1 0 2 0 5 0 0 0 1 1 1 2 1 2 0 |
1 2 3 |
Bộ thứ hai chọn và . Bộ thứ ba chọn , và . |
Bình luận