B. Макс ба Дугуй

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

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

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

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

Хэдэн сарын турш Максим ажилдаа өөрийн дуртай дугуйгаараа ирж байгаа. Дөнгөж сая тэр дугуйчдын тэмцээнд оролцоход бэлэн гэж шийдсэн.

Тэр энэ жил $n$ тэмцээн зохиогдоно гэдгийг мэднэ. $i$-р тэмцээний үеэр оролцогч $s_{i}$ цэгээс $f_{i}$ ($s_{i} < f_{i}$) цэг хүртэлх шулуун шугамны дагуу боломжит хамгийн хурднаараа дугуйтай явах ёстой.

Цаг хэмжих нь тусгай мэдрэгч болон цаг баригчийг хэрэглэхтэй холбоотой иж бүрэн процесс байна. Дугуйны урд талын дугуйг $r$ радиустай тойрог гэж бодьё. Мэдрэгчийн хэмжээ болон бүх физик нөлөө болон дугуйн өргөнийг үл тооё. Мэдрэгч дугуйн цагираг дээр байрлах буюу $r$ радиустай тойргийн тодорхой тогтмол цэг дээр байрлана. Үүний дараа тоологч тойргийн сонгогдсон цэгтэй адилаар хөдлөх буюу урагшаа явах ба тойргийн төвийг тойрно.

Эхлээд оролцогч бүр дурын $b_{i} < s_{i} - r$ буюу түүний дугуй эхлэх шугамны ард бүтнээрээ байх $b_{i}$ цэгийг сонгоно. Үүний дараа тэр явж эхлэх ба нэн даруй хамгийн их хурдруугаа хурдлах ба мэдрэгчийн координат эхлэх цэгийн координаттай тэнцэх үед буюу $ts_{i}$ цагаас хугацаа хэмжигч ажиллаж эхлэнэ. Дугуйчин дугуйгаа унаж дуусах буюу өөрийн хамгийн их хурдаараа явах ба мэдрэгчийн координат дуусах координаттай тэнцэх үед ($tf_{i}$ хугацааны агшинд) цаг хэмжигч зогсох ба эцсийн цагийг бичиж авна. Ингээд тоолуур оролцогч $tf_{i} - ts_{i}$ хугацааны хооронд дугуйгаар туулах замаа явж дууссан гэдгийг тэмдэглэж авна.

Максим математиктаа сайн ба тэр эцсийн үр дүн зөвхөн түүний хамгийн их хурд болох $v$-с хамаарахгүй ба бас түүний эхлэх цэг $b_{i}$ цэгийг сонгох сонголтоос хамаарна гэж сэжиглэсэн. Одоо Максим таниас $n$ тэмцээн бүрийн хувьд цаг баригчаар хэмжигдэж болох хамгийн бага цагийг тооцолооч гэж байна. Түүний дугуйн радиус $r$-тэй тэнцүү.

Оролт

Эхний мөрөнд гурван бүхэл тоон утга $n$, $r$ ба $v$ ($1 ≤ n ≤ 100 000, 1 ≤ r, v ≤ 10^{9}$) байх ба харгалзан тэмцээний тоо, Максын дугуйн радиус ба түүний хамгийн их хурд байна.

Дараагийн $n$ мөрөнд тэмцээнүүдийн тодорхойлолт байна. $i$-р мөрөнд хоёр бүхэл тоон утга $s_{i}$ ба $f_{i}$ ($1 ≤ s_{i} < f_{i} ≤ 10^{9}$) байх ба $i$-р тэмцээний эхлэх координат болон дуусах координат байна.

Гаралт

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

Өөрөөр: таны хариулт $a$-тай тэнцүү байсан гэе харин шүүгчийн хариулт $b$ байсан. Шалгагч программ хэрвээ байвал таны хариуг зөв гэж үзнэ.

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

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

Оролт
2 1 2
1 10
5 9
Гаралт
3.849644710502
1.106060157705
Сэтгэгдлүүдийг ачааллаж байна...