Trung tâm cà phê
Đề bài
Mô tả
Đây chỉ là một trào lưu nhất thời hay sẽ tồn tại lâu dài? Bạn không chắc, nhưng số quán cà phê mở ra ở thành phố quê bạn ngày càng tăng và rõ ràng đã trở thành một điểm hút khách. Có vẻ người ta nghiện cà phê đến mức những căn hộ ở gần nhiều quán cà phê có thể cho thuê với giá cao hơn.
Một công ty bất động sản địa phương đã để ý đến điều này. Họ muốn xác định những vị trí có giá trị nhất trong thành phố xét theo việc ở gần nhiều quán cà phê. Họ đưa cho bạn bản đồ thành phố có đánh dấu vị trí các quán cà phê. Giả sử một người bình thường chỉ sẵn lòng đi bộ một số dãy phố cố định để uống cà phê buổi sáng, bạn cần tìm vị trí mà từ đó có thể đi tới nhiều quán cà phê nhất. Thành phố của bạn được xây theo dạng lưới ô vuông, các dãy phố song song với trục bắc nam và đông tây. Vì phải đi dọc theo các con phố, khoảng cách giữa hai giao lộ và là .
Dữ liệu vào
Dữ liệu gồm nhiều bộ test, mỗi bộ test mô tả một thành phố.
Dòng đầu tiên của mỗi bộ test chứa bốn số nguyên , , và : kích thước lưới thành phố (các giao lộ có tọa độ với , ), số quán cà phê và số truy vấn .
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (, ): vị trí của quán cà phê thứ . Mỗi giao lộ có nhiều nhất một quán cà phê.
Mỗi dòng trong dòng tiếp theo chứa một số nguyên : khoảng cách lớn nhất mà một người sẵn lòng đi bộ để uống một tách cà phê.
Sau bộ test cuối cùng là một dòng chứa bốn số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test theo dạng Case i: (như trong ví dụ). Sau đó in một dòng cho mỗi truy vấn của bộ test đó, theo đúng thứ tự truy vấn. Mỗi dòng gồm số quán cà phê lớn nhất có thể đi tới với khoảng cách truy vấn (tức là có khoảng cách tới vị trí chọn không quá ), theo sau là vị trí tối ưu, viết dạng (x,y) (không có dấu cách bên trong ngoặc).
Vị trí được chọn là một giao lộ của lưới (, ). Nếu có nhiều vị trí tối ưu, chọn vị trí xa nhất về phía nam (tọa độ nhỏ nhất). Nếu vẫn còn nhiều vị trí, chọn vị trí xa nhất về phía tây (tọa độ nhỏ nhất).
Ràng buộc
- .
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 5 3 1 1 1 2 3 3 4 4 2 4 1 2 4 0 0 0 0 |
Case 1: 3 (3,4) 4 (2,2) 5 (3,1) |
Ví dụ chính thức. Với , từ đi tới được quán , , . Với , từ đi tới được quán (trừ ). Với , từ đi tới được cả quán, và không có vị trí nào có , làm được điều đó. |
| 3 3 2 2 1 3 3 1 0 2 0 0 0 0 |
Case 1: 1 (3,1) 2 (1,1) |
Với , đứng tại một quán thì đi tới được quán; có nhỏ nhất. Với , các vị trí , , đều đi tới được cả quán; chọn vì có nhỏ nhất. |
Thành phố trong ví dụ 1 (hàng trên cùng là , hàng dưới cùng là , cột trái nhất là ; ô # là quán cà phê):
grid .#.# ..#. #... #...
Bình luận