Code Submission Evaluation System Login

Datatähti-valmennus

Lyhin reitti


Task | Statistics


CSES - Lyhin reitti

Time limit:1.00 s Memory limit:128 MB

Uolevin sedän tilan ympärillä on aitaus, joka muodostuu $n$ suorasta aidasta. Aidan kärkipisteet ovat järjestyksessä $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$.

Lisäksi tiedät, että tilan päärakennus sijaitsee kohdassa $(x_p,y_p)$ ja sauna sijaitsee kohdassa $(x_s,y_s)$. Kuinka pitkä on lyhin reitti päärakennukselta saunalle, joka kulkee aitauksen sisällä?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: aitojen määrä.

Sitten syötteessä on $n$ riviä, joista jokaisella on kaksi kokonaislukua $x_i$ ja $y_i$: aidan kärkipisteen sijainti on $(x_i,y_i)$. Aitaus on monikulmio, jonka sivut eivät leikkaa toisiaan.

Viimeisellä rivillä on neljä kokonaislukua $x_p$, $y_p$, $x_s$ ja $y_s$, jotka ilmaisevat päärakennuksen ja saunan sijainnit. Ne sijaitsevat aina aitauksen sisäpuolella.

Tuloste

Tulosta lyhimmän reitin pituus päärakennukselta saunalle. Vastauksen absoluuttinen tai suhteellinen virhe tulee olla alle $10^{-6}$.

Rajat
Esimerkki

Syöte:
10
1 1
3 2
4 1
5 1
6 2
6 3
5 4
4 3
4 2
2 3
2 2 5 3


Tuloste:
3.414213562