M. Берландын такси

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

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

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

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

Поликарп хуралд оролцохоор Берландын нийслэлд ирсэн. Хоцрохгүйн тулд тэр такси дуудсан ба жолоочид төмөр замын вогзалаас хурал зохиогдож буй барилгаруу аль болох хурдан хүргэж өгөхийг хүсэв. Такси хэдхэн минутанд хөдлөнө.

Берландын нийслэл нь $w$ өргөн $l$ урттай тэгш өнцөгт талбар юм. Нисэх онгоцноос харахад энэ талбар нь зүүн доод булан нь (0, 0) цэг дээр харин баруун дээд булан нь ($w,  l$) цэг дээр байрласан тэгш өнцөгт байсан. Берландын нийслэл дахь замууд нь тасралтгүй үргэлжлэх босоо болон хэвтээ хэрчимүүд байх ба координатын тэнхлэгтэй параллель байна. Энд $w + 1$ босоо зам байх ба $l + 1$ хэвтээ зам байна. $i$-р $(0 ≤ i ≤ w)$ босоо замын төгсгөлийн цэгүүдийн координатууд нь $(i,  0)$ ба $(i,  l)$ цэгүүд байна. $j$-р $(0 ≤ j ≤ l)$ хэвтээ замын төгсгөлийн цэгүүдийн координатууд нь $(0,  j)$ ба $(w,  j)$ цэгүүд байна. Тэгш өнцөгт талбар дээрх бүхэл тоон координаттай цэг бүр замуудын уулзвар байна.

Төмөр замын вогзал нь талбарын бүхэл тоон координаттай $(x_{1},  y_{1})$ цэг дээр байрласан ба такси Поликарпыг эндээс авна. Хурал бүхэл тоон координаттай $(x_{2},  y_{2})$ цэг дээр байрласан барилгад болно.

Берландын нийслэл дахь машинууд нь зөвхөн замаар явах буюу уулзвар бүрээс машин зөвхөн ойролцоох уулзвар руу буюу зөвхөн зүүн, баруун, дээш, доош явж чадна (машинууд талбарын хүрээнээс гарахгүй).

Поликарпыг авахаар ирсэн такси хурдаа үнэмлэхүй утгаар нь $a$ хурдатгалаар нэмж мөн хасч чадах ба таксины дээд хурд нь $v_{max}$. Такси хурдаа хасахгүйгээр эргэж (эсрэг чиглэлд эргэх байсан ч) чадна.

Хотын уулзварууд дээр байрласан $n$ ширхэг хурд хэмжигчтэй цагдаагийн машин байгаа. Берландын нийслэлд зөвшөөрөгдсөн хурдны дээд хэмжээ нь $v_{p}$ ба хэрвээ уулзвар дээр цагдаа байвал таксины жолооч уулзварыг $v_{p}$-с их хурдаар нэвтрэхгүй ($(x_{i},  y_{i})$ уулзвар дээр байгаа цагдаа машины хурдыг уулзварыг нэвтрэх үед хэмждэг). Таксины жолооч хотын бусад цэгт дурын хурдаар явахыг зөвшөөрсөн учир нь энд баривчлагдах аюулгүй.

Такси $(x_{1},  y_{1})$ цэгээс тэг хурдтай хөдлөж эхлэнэ. Поликарп хоцрохоос айж байгаа ба $(x_{2},  y_{2})$ цэгт очсон мөчид таксинаас шууд үсрэн гарахаар болсон. Түүнчлэн такси замын төгсгөлийн цэгт $v_{max}$-с хэтрэхгүй ямар ч хурдаар ирж болно.

Ямар ч хоёр цагдаа нэг байрлалд байхгүй. Мөн $(x_{1},  y_{1})$ ба $(x_{2},  y_{2})$ цэгүүд дээр цагдаа байхгүй. $(x_{1},  y_{1})$ ба$(x_{2},  y_{2})$ цэгүүд нь ялгаатай.

Та такси цагдаагийн дэргэдүүр $v_{p}$-с хэтрэхгүй хурдаар явж төгсгөлийн цэгт ирэх боломжит хамгийн бага хугацааг олох хэрэгтэй.

Оролт

Оролтын эхний мөрөнд зургаан тоо $w,  l,  n,  a,  v_{max},  v_{p}$ ($1 ≤ w,  l ≤ 100,  0 ≤ n ≤ 100, $ $0.01 ≤ a ≤ 5.00,  1 ≤ v_{max},  v_{p} ≤ 100$) байна. $a$ нь бутархай тоо ба цэгээс хойш яг хоёр оронгийн нарийвчлалтай өгөгдөх ба үүнээс бусад бүх тоо бүхэл тоо байна.

Оролтын хоёр дахь мөрөнд дөрвөн бүхэл тоо $x_{1},  y_{1},  x_{2},  y_{2}$ $(0 ≤ x_{1},  x_{2} ≤ w,  0 ≤ y_{1},  y_{2} ≤ l)$ байх ба энд $(x_{1},  y_{1})$ нь эхлэлийн цэгийн координат бол $(x_{2},  y_{2})$ нь төгсгөлийн цэгийн координат юм.

Дараагийн $n$ мөр бүрт хоёр бүхэл тоон утга $x_{i},  y_{i}$ $(0 ≤ x_{i} ≤ w,  0 ≤ y_{i} ≤ l)$ байх буюу цагдаа байгаа уулзваруудын координатууд юм.

Гаралт

Гаралтанд нэг бутархай тоо байх ба энэ нь таксины жолооч Поликарпыг төмөр замын вогзалаас хурал болж буй барилгаруу хүргэхэд шаардлагатай хамгийн бага хугацаа юм. Хариултын үнэмлэхүй болон харьцангуй алдаа $10^{ - 6}$-с ихгүй байх ёстой.

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

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

Оролт
5 5 1 0.50 3 1
2 1 4 1
3 1
Гаралт
2.8284271247
Сэтгэгдлүүдийг ачааллаж байна...