D. Баавгай ба гэрэлтүүлэгч

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэг өдөр баавгай $Oxy$ тэнхлэг дээр амьдарсан. Тэр харанхуйгаас айсан байсан ба шөнөөр гэрэлтэхгүй байгаа хавтгайн цэгүүдийн дагуу явж чадахгүй байсан. Нэг өдөр баавгай $(l, 0)$ цэгт байрлах өөрийн байшингаас $(r, 0)$ цэгт байрлах найзынхаа байшинруу $(r - l)$ урттай хэсгийн дагуу шөнө алхахыг хүссэн. Мэдээж хэрвээ тэр ингэж алхахыг хүсвэл тэр уг хэсгийн цэг бүрийг гэрэлтүүлэх хэрэгтэй. Иймээс баавгай найзаасаа тусламж хүсэн дуудсан (тиймээ шөнө дунд).

$Oxy$ тэнхлэг нь $n$ гэрэлтүүлэгч агуулсан. $i$-р гэрэлтүүлэгч нь $(x_{i}, y_{i})$ цэгт байрлах ба хавтгайн $(x_{i}, y_{i})$ цэгээс дурын $a_{i}$ өнцөг бүхий хэсгийг гэрэлтүүлж чадна. Баавгай найзаасаа манай гэрээс баавгайн явах замын хэсгийг аль болох гэрээсээ хол явж болохуйцаар гэрэлтүүлэгчдийг эргүүлж өгөхийг гуйсан. Түүний ухаалаг найз түүний хүсэлтийг биелүүлэхээр болсон. Энэ хойгуур баавгай гэрээсээ хамгийн холдоо хэр хол явах боломжтой вэ гэж гайхсан. Түүнд энэ зайг олоход туслана уу. The $Oxy$ axis contains $n$ floodlights. Floodlight $i$ is at point $(x_{i}, y_{i})$ and can light any angle of the plane as large as $a_{i}$ degree with vertex at point $(x_{i}, y_{i})$. The bear asked his friend to turn the floodlights so that he (the bear) could go as far away from his house as possible during the walking along the segment. His kind friend agreed to fulfill his request. And while he is at it, the bear wonders: what is the furthest he can go away from his house? Hep him and find this distance.

Хавтгайд ямар нэг гэрэл хаах зүйл байхгүй гэж үзэх ба гэрэлтүүлэгчдээс өөр гэрэл үүсгэгч байхгүй. Баавгайн найз баавгайг явж байхад гэрэлтүүлэгчдийг эргүүлж чадахгүй. Бүх гэрэлтүүлэгч зөв чиглэлрүү харсны дараа баавгай алхах ба түүний найз унтана.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан гурван бүхэл тоо $n$, $l$, $r$ $(1 ≤ n ≤ 20;  - 10^{5} ≤ l ≤ r ≤ 10^{5})$ байна. Дараагийн $n$ мөрийн $i$-р мөрт зайгаар тусгаарлагдсан гурван бүхэл тоо $x_{i}$, $y_{i}$, $a_{i}$ $( - 1000 ≤ x_{i} ≤ 1000; 1 ≤ y_{i} ≤ 1000; 1 ≤ a_{i} ≤ 90)$ байх буюу гэрэлтүүлэгчдийн тодорхойлолт байна.

Хоёр гэрэлтүүлэгч хавтгайн нэг цэг дээр байж болно.

Гаралт

Бодлогын хариу болох нэг бодит тоог хэвлэ. Хариултын харьцангуй эсвэл үнэмлэхүй алдаа нь $10^{ - 6}$-с ихгүй тохиолдолд зөвд тооцно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
2 3 5
3 1 45
5 1 45
Гаралт
2.000000000
Оролт
1 0 1
1 1 30
Гаралт
0.732050808
Оролт
1 0 1
1 1 45
Гаралт
1.000000000
Оролт
1 0 2
0 2 90
Гаралт
2.000000000

Тэмдэглэл

Эхний жишээн дээр боломжит нэг шийдэл нь:

Хоёр дахь жишээн дээр ганцхан шийдэл байгаа нь:

Гурав дахь жишээн дээр ганцхан шийдэл байгаа нь:

Сэтгэгдлүүдийг ачааллаж байна...