CSES - Lyhin reitti
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Uolevin sedän tilan ympärillä on aitaus, joka muodostuu nn suorasta aidasta. Aidan kärkipisteet ovat järjestyksessä (x1,y1),(x2,y2),,(xn,yn)(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n).

Lisäksi tiedät, että tilan päärakennus sijaitsee kohdassa (xp,yp)(x_p,y_p) ja sauna sijaitsee kohdassa (xs,ys)(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 nn: aitojen määrä.

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

Viimeisellä rivillä on neljä kokonaislukua xpx_p, ypy_p, xsx_s ja ysy_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 10610^{-6}.

Rajat

  • 3n1003 \le n \le 100
  • kaikki koordinaatit ovat välillä 106106-10^6 \ldots 10^6

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