trang chủ / đề bài / icpcwf11_e

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ộ (a,b) và (c,d) là |a−c|+|b−d|.

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 dx, dy, n và q: kích thước lưới thành phố dx×dy (các giao lộ có tọa độ (x,y) với 1≤x≤dx, 1≤y≤dy), số quán cà phê n và số truy vấn q.

Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên xi và yi (1≤xi≤dx, 1≤yi≤dy): vị trí của quán cà phê thứ i. Mỗi giao lộ có nhiều nhất một quán cà phê.

Mỗi dòng trong q dòng tiếp theo chứa một số nguyên m: 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ố 0.

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 m (tức là có khoảng cách tới vị trí chọn không quá m), 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 (1≤x≤dx, 1≤y≤dy). Nếu có nhiều vị trí tối ưu, chọn vị trí xa nhất về phía nam (tọa độ y 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 độ x nhỏ nhất).

Ràng buộc

  • 1≤dx,dy≤1000.
  • 0≤n≤5·105.
  • 1≤q≤20.
  • 0≤m≤106.

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 m=1, từ (3,4) đi tới được 3 quán (3,3), (4,4), (2,4). Với m=2, từ (2,2) đi tới được 4 quán (trừ (4,4)). Với m=4, từ (3,1) đi tới được cả 5 quán, và không có vị trí nào có y=1, x<3 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 m=0, đứng tại một quán thì đi tới được 1 quán; (3,1) có y nhỏ nhất. Với m=2, các vị trí (1,1), (2,2), (3,3) đều đi tới được cả 2 quán; chọn (1,1) vì có y nhỏ nhất.

Thành phố trong ví dụ 1 (hàng trên cùng là y=4, hàng dưới cùng là y=1, cột trái nhất là x=1; ô # là quán cà phê):

grid
.#.#
..#.
#...
#...

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0