Codeforces Round #696 (Div. 2)
14:27:25 |
B. Ваня ба гэрлийн шонгууд
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Ваня $n$ ширхэг гэрлийн шон бүхий $l$ урттай гудамжаар шөнө дөлөөр ганцаараа алхаж байна. Гудамжны эхлэлийн цэг нь координатын системийн $0$ цэгт харгалздаг ба төгсгөлийн цэг нь $l$ цэгт харгалздаг гэж үзье. Тэгвэл $a_{i}$ цэгт $i$-р шон байна. Шон бүрийн гэрэлтүүлэг $d$ зайнаас хэтэрдэггүй бөгөөд бүх шонгийн хувьд энэ $d$ зай ижилхэн.
Тэгээд гэрлийн шонгууд гудамжийг бүхэлд нь гэрэлтүүлж болдогоор $d$ зайг хамгийн багадаа хэд байлгаж болох вэ гэдгийг Ваня бодсоор алхаж байлаа. Түүнийг удаан бодолд дарагдуулахгүйн тулд өмнөөс нь тооцоог нь хийж өгнө үү.
Оролт
Эхний мөр нь $n$, $l$ ($1 ≤ n ≤ 1000$, $1 ≤ l ≤ 10^{9}$) хоёр бүхэл тоог агуулна. Эдгээр нь харгалзан гэрлийн шонгийн тоо ба гудамжны урт юм.
Дараагийн мөр нь $n$ ширхэг $a_{i}$ ($0 ≤ a_{i} ≤ l$) бүхэл тоонуудыг агуулна. Гэрэлтүүлгүүд гудамжны төгсгөлд байрласан байж болно.
Гаралт
Гудамжийг бүхэлд нь гэрэлтүүлэхэд хэрэгтэй хамгийн бага радиус $d$-г хэвлэнэ. Энэ хариу системийн хариунаас $10^{-9}$-аас багаар зөрж болно.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
7 15 15 5 3 7 9 14 0
Гаралт
2.5000000000
Оролт
2 5 2 5
Гаралт
2.0000000000
Тэмдэглэл
Хоёр дахь жишээг авч үзье. $d = 2$ үед эхний гэрэлтүүлэг гудамжны $[0, 4]$ хэсгийг, хоёр дахь гэрэлтүүлэг $[3, 5]$ хэсгийг гэрэлтүүлж чадна. Ингээд гудамж бүхэлдээ гэрэлтэй болно.