Hành Lang An Toàn

Binary-search Buổi 67-68 — Mock IOI
Points
90
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề bài

Một hành lang hình chữ nhật có chiều dài $L$ (từ $x = 0$ đến $x = L$) và chiều rộng $W$ (từ $y = 0$ đến $y = W$). Bên trong hành lang có $N$ cột cảm biến đặt tại các tọa độ $(x_i, y_i)$.

Một robot hình tròn có bán kính $R$ cần di chuyển liên tục từ cửa vào bên trái ($x = 0$) đến cửa ra bên phải ($x = L$) mà toàn bộ hình tròn luôn nằm trong hành lang ($0 \le y \le W$, ngoại trừ phần ra vào ở $x=0$ và $x=L$) và không chứa bất kỳ cột cảm biến nào ở phần bên trong hình tròn.

Hãy tìm bán kính $R$ lớn nhất của robot có thể đi qua hành lang.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên $L, W, N$ ($1 \le L, W \le 10^6$, $1 \le N \le 500$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ ($0 < x_i < L$, $0 < y_i < W$) là tọa độ cột cảm biến thứ $i$.

Kết quả

  • In ra một số thực duy nhất là bán kính $R$ lớn nhất tìm được, làm tròn đến $6$ chữ số sau dấu phẩy (sai số không quá $10^{-5}$).

Subtasks

  • Subtask 1 (30%): $N \le 20$.
  • Subtask 2 (70%): Không có ràng buộc bổ sung.

Ví dụ

Input Output
10 10 1
5 5
2.500000
Draft saved