E. Усан онгоцны хамгийн богино зам

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

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

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

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

Та нэгэн шинэ даалгавартай болсон ба энэ нь ихээхэн сонирхолтой даалгавар байв. Та усан онгоцны ахмад бөгөөд таны эхний даалгавар бол өөрийн онгоцоо нэг цэгээс өөр нэг цэг уруу аваачих юм. Мэдээж хэрэг та үүнийг хийхийн тулд хамгийн бага зардал гаргах хэрэгтэй.

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

Та зөвхөн аюулгүй цэгүүд уруу л явж болно. Тодруулбал хэрэв ямар нэгэн цэг нь гарааны болон барианы цэгүүдийн хооронд байх шулуун дээр оршиж байх юм уу арлын ирмэг дээр оршин байвал бид уг цэгийг аюулгүй цэг гэж нэрлэх юм.

Гэвч та үнэхээр азтай нэгэн ба танд маш сэргэлэн бөгөөд хүчирхэг хэдэн ажилчид байв. Иймд тэд таны аялалд туслах бөгөөд таны усан онгоцыг хөдлөхөд туслах юм. Тодруулбал далай дээр хөдөлж буй нэгж хөдөлгөөн бүрд тэд 1 Египет паунд авах ба мөн тэд таны онгоцыг арал дээгүүр өргөн авч явж чадах (тийм ээ тэд маш хүчирхэг) бөгөөд арал дээгүүр авч явж буй нэгж хөдөлгөөн бүрд тэд 2 Египет паунд авах ажээ. Таны ажилчид өгөх мөнгийг тэд хувааж авах тул ажилчдын тоо энд хамаагүй гэж үзнэ үү.

Та усан онгоцоо арлын ирмэг дээгүүр явуулж болох бөгөөд үүнийг далай дээр явж байна гэж үзэх юм.

Танд одоо уг далайн газрын зураг байгаа бөгөөд та өөрийн аяллын хамгийн бага зардлыг тооцох хэрэгтэй болжээ.

Таны аяллын эхлэлийн цэг ($xStart$, $yStart$) болон төгсгөлийн цэг ($xEnd$, $yEnd$) нар нь ялгаатай цэгүүд байхыг анхаарна уу.

Арал гэдэг нь гүдгэр олон өнцөгт байх бөгөөд нэг ижил шулуун дээр уг олон өнцөгтийн 2-оос олонгүй орой оршин байх юм. Мөн аяллын эхлэлийн цэг болон төгсгөлийн цэгүүд нь уг арлын ирмэг дээр эсвэл дотор байрлаагүй байна. Олон өнцөгтийн цэгүүд нь цагийн зүүний эсрэг дарааллын дагуу өгөгдөнө.

Оролт

Эхний мөрөнд 4-н бүхэл тоо $xStart$, $yStart$, $xEnd$ болон $yEnd$ ($ - 100 ≤ xStart, yStart, xEnd, yEnd ≤ 100$) өгөгдөнө. 2-дахь мөрөнд бүхэл тоо $n$ өгөгдөх ба энэ нь олон өнцөгтийн оройн тоог илэрхийлнэ. Үүний дараа $n$ ширхэг хос бүхэл тоонууд буюу $x$ болон $y$-уудыг ($ - 100 ≤ x, y ≤ 100$) агуулах нэгэн мөр өгөгдөх ба эдгээр хос бүхэл тоонууд нь олон өнцөгтийн оройнуудын координатуудыг илэрхийлэх юм. Мөн олон өнцөгтийн оройнууд нь ялгаатай байна.

Гаралт

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

Орчуулсан: Баатархүү

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

Оролт
1 7 6 7
4
4 2 4 12 3 12 3 2
Гаралт
6.000000000
Оролт
-1 0 2 0
4
0 0 1 0 1 1 0 1
Гаралт
3.000000000
Сэтгэгдлүүдийг ачааллаж байна...