Hướng giải: Thử nghiệm bom

Tiến hành sắp xếp các tọa độ cột mốc theo thứ tự tăng dần. Với mỗi lần thử nghiệm, tìm chỉ số ~i~ nhỏ nhất thỏa mãn tọa độ cột mốc thứ ~i~ lớn hơn hoặc bằng ~z~ và chỉ số ~j~ lớn nhất thỏa mãn tọa độ cột mốc thứ ~j~ nhỏ hơn hoặc bằng ~z~ thông qua Tìm kiếm nhị phân. Khi đó:

• Các cột mốc có chỉ số trong đoạn ~[i,n]~ trùng hoặc nằm bên phải vị trí đặt bom.
• Các cột mốc có chỉ số trong đoạn ~[1,j]~ trùng hoặc nằm bên trái vị trí đặt bom.

Bán kính ~r~ tối thiểu chính là khoảng cách giữa vị trí đặt bom đến cột mốc chỉ số ~1~ (nếu chọn hướng trái) hoặc đến cột mốc chỉ số ~n~ (nếu chọn hướng phải).

Độ phức tạp: ~O(n.log(n)+m.log(n))~.