Đèn Lồng Phố Cổ
Problem
Đêm rằm tháng Tám, câu lạc bộ của Khoa được giao trang trí con đường ven sông ở phố cổ. Con đường thẳng tắp, dài đúng \(L\) mét. Ta coi con đường là đoạn thẳng \([0, L]\) trên trục số, đầu đường ở vị trí \(0\) và cuối đường ở vị trí \(L\).
Các bạn trong câu lạc bộ đã treo sẵn \(n\) chiếc đèn lồng dọc con đường, chiếc đèn thứ \(i\) treo ở vị trí \(x_i\). Vì mỗi bạn treo một kiểu nên có chỗ treo dày đặc, có chỗ treo trùng hẳn lên nhau, có đoạn lại bị bỏ quên.
Khoa đặt mua một loại bóng đèn chỉnh được độ sáng. Khi chỉnh tới mức \(d\), một chiếc đèn treo ở vị trí \(x\) sẽ chiếu sáng đoạn đường \([x - d, x + d]\). Mọi chiếc đèn phải dùng chung một mức \(d\).
Ban tổ chức yêu cầu: mọi điểm trên con đường, kể cả đầu đường và cuối đường, đều phải được chiếu sáng bởi ít nhất một chiếc đèn.
Đèn càng sáng càng tốn điện, nên Khoa muốn chọn \(d\) nhỏ nhất thỏa mãn yêu cầu trên. Bạn hãy giúp Khoa nhé.
"Treo đèn thì dễ, treo sao cho đủ sáng mà không phí điện mới khó."
-- Khoa, lúc nhận hóa đơn tiền điện
Input
- Dòng đầu tiên gồm hai số nguyên \(n, L\) \((1 \leq n \leq 10^5, 1 \leq L \leq 10^9)\) lần lượt là số đèn lồng và chiều dài con đường.
- Dòng thứ hai gồm \(n\) số nguyên \(x_1, x_2, \dots, x_n\) \((0 \leq x_i \leq L)\) là vị trí của các đèn lồng. Các vị trí không nhất thiết được sắp xếp và có thể trùng nhau.
Output
- In ra một số thực duy nhất là giá trị \(d\) nhỏ nhất tìm được. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối so với đáp án của ban giám khảo không vượt quá \(10^{-6}\).
Sample
| # | Input | Output |
|---|---|---|
| 1 | | |
| 2 | | |
Note
Sample 1: các đèn nằm ở \(0, 6, 10\). Đoạn tối dài nhất là từ \(0\) đến \(6\). Với \(d = 3\), đèn ở \(0\) chiếu tới \(3\) và đèn ở \(6\) chiếu ngược lại tới \(3\), vừa khít. Đoạn từ \(6\) đến \(10\) dài \(4\) nên cũng được phủ kín. Hai đầu đường đều có đèn nên không có vấn đề gì.
Sample 2: sau khi sắp xếp, các đèn nằm ở \(3, 3, 9, 15\). Các khoảng trống giữa hai đèn liên tiếp dài \(0, 6, 6\) nên chỉ cần \(d = 3\) là đủ cho phần giữa. Nhưng đầu đường cách đèn gần nhất \(3\) mét, còn cuối đường (vị trí \(20\)) cách đèn gần nhất tới \(5\) mét. Vì vậy \(d\) nhỏ nhất là \(5\).
Bạn có thể in đáp án với bao nhiêu chữ số thập phân tùy ý, miễn là đủ chính xác. Ví dụ ở Sample 2, các cách in 5, 5.0 hay 5.000000 đều được chấp nhận.
Code editor
Sign in to write and submit your solution.
Log in
Comments