Keçmək
Uzun və düz bir dəhliz bir sıra sensorlarla təchiz olunub. Hər bir sensorun müəyyən bir diapazonu var ki, bu diapazonda obyektləri və ya şəxsləri aşkar edə bilir. Əgər obyektin bir hissəsi sensorun diapazonunda olarsa, siqnal işə düşəcək. Əks halda, heç nə baş verməyəcək.
Ethan bu dəhlizdən keçərək digər tərəfdə bəzi casus işlərini görməlidir. Sual budur ki, o, dəhlizdən aşkar edilmədən keçə bilərmi? O, o qədər asanlıqla sığa bilərmi ki, bəzi avadanlıqları da özü ilə gətirə bilsin, yoxsa dar paltar geyinməlidir? Yoxsa bəlkə bir robot göndərə bilər?
Biz dəhlizi iki ölçülü (hündürlüyü nəzərə almırıq) olaraq modelləşdiririk, iki düz xəttlə məhdudlaşdırılmışdır. Hər bir sensor dəhlizin içərisində və ya divarda yerləşir. Onların diapazonları dəhlizin iki ucu arasında yaxşı yerləşir. Dəhlizdən keçən şəxsi və ya robotu dairə kimi modelləşdiririk. Verilən düzülüşə görə, bu dairənin maksimum radiusu nə qədər ola bilər ki, dəhlizi aşkar edilmədən keçmək mümkün olsun?
Nümunələrin vizual təsviri.
Giriş verilənləri
Birinci sətirdə bir müsbət ədəd: test hallarının sayı, ən çox 100. Bundan sonra hər test halı üçün:
bir sətirdə tək tam ədəd w (1 ≤ w ≤ 100000): dəhlizin eni. İki divar x = 0 və x = w xətləri ilə verilir.
bir sətirdə tək tam ədəd n (0 ≤ n ≤ 1000): dəhlizdəki sensorların sayı.
n sətirdə üç boşluqla ayrılmış tam ədəd x, y və r (0 ≤ x ≤ w, -100000 ≤ y ≤ 100000 və 1 ≤ r ≤ 100000): hər bir sensorun yeri və diapazonu, müvafiq olaraq.
Dəhlizin iki ucu y = -1 və y = +1 nöqtələrindədir, yəni texniki baxımdan, bütün sensorların diapazonundan çox uzaqdadırlar.
Çıxış verilənləri
Hər test halı üçün:
bir sətirdə bir ondalık nöqtə ədədi: dəhlizdən aşkar edilmədən keçə biləcək ən böyük dairəvi obyektin (və ya şəxsin) radiusu, obyektin tam dəqiqliklə hərəkət etdirilə biləcəyini nəzərə alaraq. Əgər heç nə keçə bilməzsə, çıxış sıfır olmalıdır.
Ədəd 10^{-6 } dəqiqliklə dəqiq olmalıdır.