D. Аалз

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

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

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

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

1-с $n$ хүртэл дугаарлагдсан $n$ оройгоос бүрдэх өөртэйгээ огтлолцоогүй, гүдгэр байх албагүй олон өнцөгт бүхий талбар байна. Уг олон өнцөгтийн хүрээн дээр нэг аалз байх ба аалз нь дараах байдлаар хөдлөнө:

  1. Шилжих. Аалз олон өнцөгтийн хүрээн дээр байрласан $(x_{1}, y_{1})$ координаттай $p_{1}$ цэгээс мөн олон өнцөгтийн хүрээн дээр байрлах $(x_{2}, y_{2})$ координаттай $p_{2}$ цэгрүү очно. Аалз олон өнцөгтийн хүрээнээс гарч явахгүй ба аалзны $p_{1}$ цэгээс $p_{2}$ цэг хүрэх зам нь олон өнцөгтийн хүрээний дагуу байна. Харин аалз аль зүгт ч явж болно (цагийн зүүний дагуу, эсрэг).
  2. Доошлох. Аалз $(x_{1}, y_{1})$ координаттай $p_{1}$ цэгээс $(x_{2}, y_{2})$ координаттай $p_{2}$ цэгрүү очно. Энд $p_{1}$ болон $p_{2}$ цэгүүд нь нэг босоо шулуунд байрлах ёстой ($x_{1} = x_{2}$) ба $p_{1}$ цэг нь $p_{2}$ цэгээс доод түвшинд байрлахгүй, мөн $p_{1}p_{2}$ сегментэд олон өнцөгтөөс гадна орших ямар ч цэг байх ёсгүй (сегмент хүрээтэй давхардсан цэгүүдтэй байж болно).

Анх аалз олон өнцөгтийн $s$ дугаартай орой дээр байрлана. Шилжилт болон доошлолтуудаас бүрдсэн $t$ орой хүртэлх хамгийн богино замын уртыг олно уу. Зайг тооцоолохдоо энгийн Эвклидийн хэмжээсийг ашиглана .

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($3 ≤ n ≤ 10^{5}$) байх ба өгөгдсөн олон өнцөгтийн оройнуудын тоо. Дараагийн $n$ мөр бүрт зайгаар тусгаарлагдсан хоёр бүхэл тоо байх буюу олон өнцөгтийн оройнуудын координат юм. Оройнуудыг цагийн зүүний эсрэг дараалалтайгаар жагсаана. Олон өнцөгтийн оройнуудын координатууд үнэмлэхүй утгаараа $10^{4}$-с хэтрэхгүй.

Сүүлийн мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $s$ ба $t$ ($1 ≤ s, t ≤ n$) байх ба хамгийн богино замыг олох гэж буй замын эхлэх болон дуусах оройнуудын дугаар юм.

Олон өнцөгтийн оройнууд нь оролтонд өгсөн дарааллаараа дугаарлагдах буюу эхний оройн координат оролтын хоёрдугаар мөрөнд харин $n$-р оройн координат $(n + 1)$-р мөрөнд байрлана. Өгөгдсөн олон өнцөгт нь энгийн байх буюу өөртэйгээ огтлолцохгүй эсвэл өөртэйгээ шүргэлцэхгүй.

Гаралт

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

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

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

Оролт
4
0 0
1 0
1 1
0 1
1 4
Гаралт
1.000000000000000000e+000
Оролт
4
0 0
1 1
0 2
-1 1
3 3
Гаралт
0.000000000000000000e+000
Оролт
5
0 0
5 0
1 4
0 2
2 1
3 1
Гаралт
5.650281539872884700e+000

Тэмдэглэл

Эхний жишээн дээр аалз 1 болон 4 оройг холбож буй талын дагуу шилжинэ.

Хоёр дахь жишээн дээр аалз хаашаа ч шилжих шаардлагагүй ба зай нь тэгтэй тэнцүү.

Гурав дахь жишээн дээр аалзны хувьд шилдэг стратеги нь 3 дугаартай оройгоос (2,3) шилжиж, (2,1) цэгрүү доошлоод, тэгээд 1 дугаартай оройруу шилжих юм.

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