← Home
For problem statement at 0-999/200-299/220-229/223/problemD.txt this is a correct solution, but verifier at 0-999/200-299/220-229/223/verifierD.go ends with case 1 failed: runtime error: exit status 2
panic: runtime error: index out of range [5] with length 5

goroutine 1 [running]:
main.main()
	/tmp/build-42987048/solution.go:330 +0x1884

exit status 1 can you fix the verifier? ```go
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"math"
	"math/rand"
	"os"
	"sort"
	"strconv"
)

type Point struct {
	x, y int64
}

type Edge struct {
	id   int
	L, R Point
}

func (e Edge) yAt(x int64) float64 {
	return float64(e.L.y) + float64(e.R.y-e.L.y)*float64(x-e.L.x)/float64(e.R.x-e.L.x)
}

func compareEdges(e1, e2 Edge) int {
	if e1.id == e2.id {
		return 0
	}
	xMin := float64(e1.L.x)
	if float64(e2.L.x) > xMin {
		xMin = float64(e2.L.x)
	}
	xMax := float64(e1.R.x)
	if float64(e2.R.x) < xMax {
		xMax = float64(e2.R.x)
	}
	xMid := (xMin + xMax) / 2.0
	y1 := float64(e1.L.y) + float64(e1.R.y-e1.L.y)*(xMid-float64(e1.L.x))/float64(e1.R.x-e1.L.x)
	y2 := float64(e2.L.y) + float64(e2.R.y-e2.L.y)*(xMid-float64(e2.L.x))/float64(e2.R.x-e2.L.x)
	if y1 < y2 {
		return -1
	} else if y1 > y2 {
		return 1
	} else {
		return e1.id - e2.id
	}
}

type TreapNode struct {
	e        Edge
	priority int
	left     *TreapNode
	right    *TreapNode
}

func split(root *TreapNode, e Edge) (*TreapNode, *TreapNode) {
	if root == nil {
		return nil, nil
	}
	if compareEdges(root.e, e) < 0 {
		l, r := split(root.right, e)
		root.right = l
		return root, r
	} else {
		l, r := split(root.left, e)
		root.left = r
		return l, root
	}
}

func merge(l, r *TreapNode) *TreapNode {
	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 insertNode(root *TreapNode, e Edge) *TreapNode {
	node := &TreapNode{e: e, priority: rand.Int()}
	l, r := split(root, e)
	return merge(merge(l, node), r)
}

func deleteNode(root *TreapNode, e Edge) *TreapNode {
	if root == nil {
		return nil
	}
	cmp := compareEdges(root.e, e)
	if cmp == 0 {
		return merge(root.left, root.right)
	} else if cmp < 0 {
		root.right = deleteNode(root.right, e)
	} else {
		root.left = deleteNode(root.left, e)
	}
	return root
}

func findAbove(root *TreapNode, x int64, y float64) *Edge {
	var best *Edge
	curr := root
	for curr != nil {
		ey := curr.e.yAt(x)
		if ey > y {
			best = &curr.e
			curr = curr.left
		} else {
			curr = curr.right
		}
	}
	return best
}

func findBelow(root *TreapNode, x int64, y float64) *Edge {
	var best *Edge
	curr := root
	for curr != nil {
		ey := curr.e.yAt(x)
		if ey < y {
			best = &curr.e
			curr = curr.right
		} else {
			curr = curr.left
		}
	}
	return best
}

func isInside(prev, V, next, D Point) bool {
	v1 := Point{next.x - V.x, next.y - V.y}
	v2 := Point{prev.x - V.x, prev.y - V.y}
	cross := v1.x*v2.y - v1.y*v2.x
	c1 := v1.x*D.y - v1.y*D.x
	c2 := D.x*v2.y - D.y*v2.x
	if cross > 0 {
		return c1 > 0 && c2 > 0
	} else if cross < 0 {
		return c1 > 0 || c2 > 0
	} else {
		return c1 > 0
	}
}

type NodeInfo struct {
	id int
	x  int64
	y  float64
}

type GraphEdge struct {
	to     int
	weight float64
}

type Item struct {
	id   int
	dist float64
	idx  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].idx = i
	pq[j].idx = j
}
func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)
	item.idx = len(*pq)
	*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.idx = -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
	}

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())

	V := make([]Point, n+1)
	for i := 1; i <= n; i++ {
		V[i] = Point{int64(nextInt()), int64(nextInt())}
	}
	S := nextInt()
	T := nextInt()

	adj := make([][]GraphEdge, 3*n+5)
	edgePoints := make([][]NodeInfo, n+1)
	nodeCount := n

	startAt := make(map[int64][]Edge)
	endAt := make(map[int64][]Edge)
	eventsMap := make(map[int64][]int)

	for i := 1; i <= n; i++ {
		eventsMap[V[i].x] = append(eventsMap[V[i].x], i)
		nextID := i + 1
		if i == n {
			nextID = 1
		}
		u, v := V[i], V[nextID]

		if u.x == v.x {
			dist := math.Hypot(float64(u.x-v.x), float64(u.y-v.y))
			adj[i] = append(adj[i], GraphEdge{to: nextID, weight: dist})
			adj[nextID] = append(adj[nextID], GraphEdge{to: i, weight: dist})
			continue
		}

		L, R := u, v
		if L.x > R.x {
			L, R = R, L
		}
		e := Edge{id: i, L: L, R: R}
		startAt[L.x] = append(startAt[L.x], e)
		endAt[R.x] = append(endAt[R.x], e)

		edgePoints[i] = append(edgePoints[i], NodeInfo{id: i, x: u.x, y: float64(u.y)})
		edgePoints[i] = append(edgePoints[i], NodeInfo{id: nextID, x: v.x, y: float64(v.y)})
	}

	var eventX []int64
	for x := range eventsMap {
		eventX = append(eventX, x)
	}
	sort.Slice(eventX, func(i, j int) bool { return eventX[i] < eventX[j] })

	var root *TreapNode

	for _, X := range eventX {
		verts := eventsMap[X]
		sort.Slice(verts, func(i, j int) bool {
			return V[verts[i]].y < V[verts[j]].y
		})

		for j, vID := range verts {
			v := V[vID]
			y := float64(v.y)

			aboveE := findAbove(root, X, y)
			yUp := math.Inf(1)
			pUpID := -1
			isEdgeUp := false

			if aboveE != nil {
				yUp = aboveE.yAt(X)
				isEdgeUp = true
			}
			if j < len(verts)-1 {
				nextY := float64(V[verts[j+1]].y)
				if nextY <= yUp {
					yUp = nextY
					pUpID = verts[j+1]
					isEdgeUp = false
				}
			}

			if yUp != math.Inf(1) {
				prev := V[vID-1]
				if vID == 1 {
					prev = V[n]
				}
				next := V[vID+1]
				if vID == n {
					next = V[1]
				}

				if isInside(prev, v, next, Point{0, 1}) {
					if isEdgeUp {
						nodeCount++
						pUpID = nodeCount
						edgePoints[aboveE.id] = append(edgePoints[aboveE.id], NodeInfo{id: pUpID, x: X, y: yUp})
					}
					adj[pUpID] = append(adj[pUpID], GraphEdge{to: vID, weight: yUp - y})
				}
			}

			belowE := findBelow(root, X, y)
			yDown := math.Inf(-1)
			pDownID := -1
			isEdgeDown := false

			if belowE != nil {
				yDown = belowE.yAt(X)
				isEdgeDown = true
			}
			if j > 0 {
				prevY := float64(V[verts[j-1]].y)
				if prevY >= yDown {
					yDown = prevY
					pDownID = verts[j-1]
					isEdgeDown = false
				}
			}

			if yDown != math.Inf(-1) {
				prev := V[vID-1]
				if vID == 1 {
					prev = V[n]
				}
				next := V[vID+1]
				if vID == n {
					next = V[1]
				}

				if isInside(prev, v, next, Point{0, -1}) {
					if isEdgeDown {
						nodeCount++
						pDownID = nodeCount
						edgePoints[belowE.id] = append(edgePoints[belowE.id], NodeInfo{id: pDownID, x: X, y: yDown})
					}
					adj[vID] = append(adj[vID], GraphEdge{to: pDownID, weight: y - yDown})
				}
			}
		}

		for _, e := range endAt[X] {
			root = deleteNode(root, e)
		}
		for _, e := range startAt[X] {
			root = insertNode(root, e)
		}
	}

	for _, pts := range edgePoints {
		if len(pts) == 0 {
			continue
		}
		sort.Slice(pts, func(i, j int) bool {
			return pts[i].x < pts[j].x
		})
		for i := 0; i < len(pts)-1; i++ {
			u := pts[i]
			v := pts[i+1]
			dist := math.Hypot(float64(u.x-v.x), u.y-v.y)
			adj[u.id] = append(adj[u.id], GraphEdge{to: v.id, weight: dist})
			adj[v.id] = append(adj[v.id], GraphEdge{to: u.id, weight: dist})
		}
	}

	dist := make([]float64, nodeCount+1)
	for i := 1; i <= nodeCount; 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)
		u := curr.id

		if curr.dist > dist[u] {
			continue
		}
		if u == T {
			break
		}

		for _, edge := range adj[u] {
			v := edge.to
			if dist[u]+edge.weight < dist[v] {
				dist[v] = dist[u] + edge.weight
				heap.Push(&pq, &Item{id: v, dist: dist[v]})
			}
		}
	}

	fmt.Printf("%.9f\n", dist[T])
}
```