package main
import (
"bufio"
"container/heap"
"fmt"
"math"
"math/rand"
"os"
"sort"
"strconv"
)
type Point struct {
X, Y int64
}
type PointF struct {
X, Y float64
}
type Segment struct {
id int
A, B Point
dir int
}
func ccw(A, B, C Point) int64 {
return (B.X-A.X)*(C.Y-A.Y) - (B.Y-A.Y)*(C.X-A.X)
}
func ccwF(seg *Segment, P PointF) float64 {
dx1 := float64(seg.B.X - seg.A.X)
dy1 := float64(seg.B.Y - seg.A.Y)
dx2 := P.X - float64(seg.A.X)
dy2 := P.Y - float64(seg.A.Y)
return dx1*dy2 - dy1*dx2
}
func compareSeg(s1, s2 *Segment) int {
if s1.id == s2.id {
return 0
}
if s1.A.X < s2.A.X {
c := ccw(s1.A, s1.B, s2.A)
if c > 0 {
return -1
}
if c < 0 {
return 1
}
c2 := ccw(s1.A, s1.B, s2.B)
if c2 > 0 {
return -1
}
if c2 < 0 {
return 1
}
return 0
} else if s1.A.X > s2.A.X {
return -compareSeg(s2, s1)
} else {
if s1.A.Y < s2.A.Y {
return -1
}
if s1.A.Y > s2.A.Y {
return 1
}
c := ccw(s1.A, s1.B, s2.B)
if c > 0 {
return -1
}
if c < 0 {
return 1
}
return 0
}
}
type Node struct {
seg *Segment
priority uint32
left *Node
right *Node
}
func split(t *Node, seg *Segment) (*Node, *Node) {
if t == nil {
return nil, nil
}
if compareSeg(t.seg, seg) < 0 {
l, r := split(t.right, seg)
t.right = l
return t, r
} else {
l, r := split(t.left, seg)
t.left = r
return l, t
}
}
func insert(t *Node, seg *Segment, priority uint32) *Node {
if t == nil {
return &Node{seg: seg, priority: priority}
}
if priority > t.priority {
l, r := split(t, seg)
return &Node{seg: seg, priority: priority, left: l, right: r}
}
if compareSeg(seg, t.seg) < 0 {
t.left = insert(t.left, seg, priority)
} else {
t.right = insert(t.right, seg, priority)
}
return t
}
func merge(l, r *Node) *Node {
if l == nil {
return r
}
if r == nil {
return l
}
if l.priority > r.priority {
l.right = merge(l.right, r)
return l
} else {
r.left = merge(l, r.left)
return r
}
}
func remove(t *Node, seg *Segment) *Node {
if t == nil {
return nil
}
if t.seg.id == seg.id {
return merge(t.left, t.right)
}
if compareSeg(seg, t.seg) < 0 {
t.left = remove(t.left, seg)
} else {
t.right = remove(t.right, seg)
}
return t
}
func findAbove(t *Node, P PointF) *Segment {
var best *Segment
for t != nil {
if ccwF(t.seg, P) < 0 {
best = t.seg
t = t.left
} else {
t = t.right
}
}
return best
}
func findBelow(t *Node, P PointF) *Segment {
var best *Segment
for t != nil {
if ccwF(t.seg, P) > 0 {
best = t.seg
t = t.right
} else {
t = t.left
}
}
return best
}
type Candidate struct {
Y float64
seg *Segment
id int
}
type Edge struct {
to int
w float64
}
type Item struct {
id int
dist float64
index int
}
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
item.index = -1
*pq = old[0 : n-1]
return item
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
nextInt := func() int {
scanner.Scan()
ans, _ := strconv.Atoi(scanner.Text())
return ans
}
nextInt64 := func() int64 {
scanner.Scan()
ans, _ := strconv.ParseInt(scanner.Text(), 10, 64)
return ans
}
n := nextInt()
pts := make([]Point, n+1)
for i := 1; i <= n; i++ {
pts[i] = Point{X: nextInt64(), Y: nextInt64()}
}
s := nextInt()
t := nextInt()
segments := make([]*Segment, n+1)
uniqueX := []int64{}
xMap := make(map[int64]bool)
for i := 1; i <= n; i++ {
p1 := pts[i]
p2 := pts[i%n+1]
if p1.X < p2.X {
segments[i] = &Segment{id: i, A: p1, B: p2, dir: 1}
} else if p1.X > p2.X {
segments[i] = &Segment{id: i, A: p2, B: p1, dir: -1}
} else {
segments[i] = &Segment{id: i, A: p1, B: p2, dir: 0}
}
if !xMap[pts[i].X] {
xMap[pts[i].X] = true
uniqueX = append(uniqueX, pts[i].X)
}
}
sort.Slice(uniqueX, func(i, j int) bool { return uniqueX[i] < uniqueX[j] })
verticesAt := make(map[int64][]int)
startsAt := make(map[int64][]int)
endsAt := make(map[int64][]int)
for i := 1; i <= n; i++ {
verticesAt[pts[i].X] = append(verticesAt[pts[i].X], i)
seg := segments[i]
if seg.dir != 0 {
startsAt[seg.A.X] = append(startsAt[seg.A.X], i)
endsAt[seg.B.X] = append(endsAt[seg.B.X], i)
}
}
nodePos := make([]PointF, 0, 3*n+5)
nodePos = append(nodePos, PointF{})
for i := 1; i <= n; i++ {
nodePos = append(nodePos, PointF{X: float64(pts[i].X), Y: float64(pts[i].Y)})
}
numNodes := n
adj := make([][]Edge, 3*n+5)
edgePoints := make([][]int, n+1)
var root *Node
for _, x := range uniqueX {
for _, id := range endsAt[x] {
root = remove(root, segments[id])
}
var cands []Candidate
xf := float64(x)
for _, vID := range verticesAt[x] {
cands = append(cands, Candidate{Y: float64(pts[vID].Y), seg: nil, id: vID})
Pf := PointF{X: xf, Y: float64(pts[vID].Y)}
up := findAbove(root, Pf)
if up != nil {
yInt := float64(up.A.Y) + float64(up.B.Y-up.A.Y)*(xf-float64(up.A.X))/float64(up.B.X-up.A.X)
cands = append(cands, Candidate{Y: yInt, seg: up, id: 0})
}
down := findBelow(root, Pf)
if down != nil {
yInt := float64(down.A.Y) + float64(down.B.Y-down.A.Y)*(xf-float64(down.A.X))/float64(down.B.X-down.A.X)
cands = append(cands, Candidate{Y: yInt, seg: down, id: 0})
}
}
sort.Slice(cands, func(i, j int) bool {
return cands[i].Y < cands[j].Y
})
var unique []Candidate
for _, c := range cands {
if len(unique) == 0 {
unique = append(unique, c)
} else {
prev := &unique[len(unique)-1]
if math.Abs(prev.Y-c.Y) > 1e-9 {
unique = append(unique, c)
} else {
if prev.seg == nil && c.seg != nil {
prev.seg = c.seg
}
}
}
}
for i := range unique {
if unique[i].id == 0 {
numNodes++
unique[i].id = numNodes
nodePos = append(nodePos, PointF{X: xf, Y: unique[i].Y})
adj = append(adj, nil)
}
if unique[i].seg != nil {
edgePoints[unique[i].seg.id] = append(edgePoints[unique[i].seg.id], unique[i].id)
}
}
for j := 0; j < len(unique)-1; j++ {
M := PointF{X: xf, Y: (unique[j].Y + unique[j+1].Y) / 2}
below := findBelow(root, M)
if below != nil && below.dir == 1 {
u := unique[j+1].id
v := unique[j].id
w := unique[j+1].Y - unique[j].Y
for len(adj) <= u || len(adj) <= v {
adj = append(adj, nil)
}
adj[u] = append(adj[u], Edge{to: v, w: w})
}
}
for _, id := range startsAt[x] {
root = insert(root, segments[id], rand.Uint32())
}
}
for i := 1; i <= n; i++ {
u := i
v := i%n + 1
ptsOnEdge := []int{u, v}
ptsOnEdge = append(ptsOnEdge, edgePoints[i]...)
sort.Slice(ptsOnEdge, func(a, b int) bool {
pA, pB := nodePos[ptsOnEdge[a]], nodePos[ptsOnEdge[b]]
if math.Abs(pA.X-pB.X) > 1e-9 {
return pA.X < pB.X
}
return pA.Y < pB.Y
})
var uPts []int
for _, p := range ptsOnEdge {
if len(uPts) == 0 || uPts[len(uPts)-1] != p {
uPts = append(uPts, p)
}
}
for k := 0; k < len(uPts)-1; k++ {
uID, vID := uPts[k], uPts[k+1]
dist := math.Hypot(nodePos[uID].X-nodePos[vID].X, nodePos[uID].Y-nodePos[vID].Y)
for len(adj) <= uID || len(adj) <= vID {
adj = append(adj, nil)
}
adj[uID] = append(adj[uID], Edge{to: vID, w: dist})
adj[vID] = append(adj[vID], Edge{to: uID, w: dist})
}
}
dist := make([]float64, numNodes+1)
for i := 1; i <= numNodes; i++ {
dist[i] = math.Inf(1)
}
dist[s] = 0
pq := make(PriorityQueue, 0)
heap.Push(&pq, &Item{id: s, dist: 0})
for pq.Len() > 0 {
curr := heap.Pop(&pq).(*Item)
if curr.dist > dist[curr.id] {
continue
}
if curr.id == t {
break
}
for _, edge := range adj[curr.id] {
if dist[curr.id]+edge.w < dist[edge.to] {
dist[edge.to] = dist[curr.id] + edge.w
heap.Push(&pq, &Item{id: edge.to, dist: dist[edge.to]})
}
}
}
fmt.Printf("%.6f\n", dist[t])
}