← 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 All tests passed can you fix the verifier? ```go
package main

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

type Point struct {
	x, y int
}

type Segment struct {
	id    int
	A, B  Point
	OrigA Point
}

type Node struct {
	seg      *Segment
	priority uint32
	left     *Node
	right    *Node
}

var randSeed uint32 = 12345

func fastRand() uint32 {
	randSeed ^= randSeed << 13
	randSeed ^= randSeed >> 17
	randSeed ^= randSeed << 5
	return randSeed
}

func evalY(s *Segment, X int64) (int64, int64) {
	dx := int64(s.B.x - s.A.x)
	dy := int64(s.B.y - s.A.y)
	num := int64(s.A.y)*dx + dy*(X-int64(s.A.x))
	return num, dx
}

func lessThan(s1, s2 *Segment, X int64) bool {
	n1, d1 := evalY(s1, X)
	n2, d2 := evalY(s2, X)
	return n1*d2 < n2*d1
}

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 split(t *Node, seg *Segment, X int64) (*Node, *Node) {
	if t == nil {
		return nil, nil
	}
	if lessThan(seg, t.seg, X) {
		l, r := split(t.left, seg, X)
		t.left = r
		return l, t
	} else {
		l, r := split(t.right, seg, X)
		t.right = l
		return t, r
	}
}

func insert(t *Node, seg *Segment, X int64) *Node {
	l, r := split(t, seg, X)
	nn := &Node{seg: seg, priority: fastRand()}
	return merge(merge(l, nn), r)
}

func deleteNode(t *Node, seg *Segment, X int64) *Node {
	if t == nil {
		return nil
	}
	if t.seg.id == seg.id {
		return merge(t.left, t.right)
	}
	if lessThan(seg, t.seg, X) {
		t.left = deleteNode(t.left, seg, X)
	} else {
		t.right = deleteNode(t.right, seg, X)
	}
	return t
}

func findUp(t *Node, X int64, Y int64) *Segment {
	var best *Segment
	for t != nil {
		n, d := evalY(t.seg, X)
		if n > Y*d {
			best = t.seg
			t = t.left
		} else {
			t = t.right
		}
	}
	return best
}

func findDown(t *Node, X int64, Y int64) *Segment {
	var best *Segment
	for t != nil {
		n, d := evalY(t.seg, X)
		if n < Y*d {
			best = t.seg
			t = t.right
		} else {
			t = t.left
		}
	}
	return best
}

func strictlyInsideUp(V, Vprev, Vnext Point) bool {
	B := Point{Vnext.x - V.x, Vnext.y - V.y}
	A := Point{Vprev.x - V.x, Vprev.y - V.y}
	cpBA := int64(B.x)*int64(A.y) - int64(B.y)*int64(A.x)
	if cpBA > 0 {
		return B.x > 0 && A.x < 0
	} else if cpBA < 0 {
		return !(A.x >= 0 && B.x <= 0)
	}
	return B.x > 0
}

func strictlyInsideDown(V, Vprev, Vnext Point) bool {
	B := Point{Vnext.x - V.x, Vnext.y - V.y}
	A := Point{Vprev.x - V.x, Vprev.y - V.y}
	cpBA := int64(B.x)*int64(A.y) - int64(B.y)*int64(A.x)
	if cpBA > 0 {
		return B.x < 0 && A.x > 0
	} else if cpBA < 0 {
		return !(A.x <= 0 && B.x >= 0)
	}
	return B.x < 0
}

type Event struct {
	X      int
	starts []*Segment
	ends   []*Segment
	verts  []int
}

type Descend struct {
	fromPc, toPc float64
	weight       float64
}

type PQItem struct {
	node int
	dist float64
}

type PriorityQueue []*PQItem

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] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*PQItem)) }
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

type Edge struct {
	to int
	w  float64
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(reader, &n)

	V := make([]Point, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &V[i].x, &V[i].y)
	}
	var s, t int
	fmt.Fscan(reader, &s, &t)
	sIdx, tIdx := s-1, t-1

	perimeterPrefix := make([]float64, n+1)
	perimeterPrefix[0] = 0
	for i := 0; i < n; i++ {
		next := (i + 1) % n
		dist := math.Hypot(float64(V[next].x-V[i].x), float64(V[next].y-V[i].y))
		perimeterPrefix[i+1] = perimeterPrefix[i] + dist
	}
	L := perimeterPrefix[n]

	var segments []*Segment
	for i := 0; i < n; i++ {
		next := (i + 1) % n
		A, B := V[i], V[next]
		if A.x == B.x {
			continue
		}
		seg := &Segment{id: i, OrigA: A, A: A, B: B}
		if seg.A.x > seg.B.x {
			seg.A, seg.B = seg.B, seg.A
		}
		segments = append(segments, seg)
	}

	eventsMap := make(map[int]*Event)
	for i := 0; i < n; i++ {
		x := V[i].x
		if eventsMap[x] == nil {
			eventsMap[x] = &Event{X: x}
		}
		eventsMap[x].verts = append(eventsMap[x].verts, i)
	}
	for _, seg := range segments {
		eventsMap[seg.A.x].starts = append(eventsMap[seg.A.x].starts, seg)
		eventsMap[seg.B.x].ends = append(eventsMap[seg.B.x].ends, seg)
	}

	var XSorted []int
	for x := range eventsMap {
		XSorted = append(XSorted, x)
	}
	sort.Ints(XSorted)

	var root *Node
	var descends []Descend

	for _, X := range XSorted {
		ev := eventsMap[X]
		for _, seg := range ev.ends {
			root = deleteNode(root, seg, int64(X))
		}

		for _, vIdx := range ev.verts {
			v := V[vIdx]
			vY := int64(v.y)

			segUp := findUp(root, int64(X), vY)
			segDown := findDown(root, int64(X), vY)

			minYUp := int64(math.MaxInt64)
			minYUpID := -1
			maxYDown := int64(math.MinInt64)
			maxYDownID := -1

			for _, uIdx := range ev.verts {
				U := V[uIdx]
				if U.y > v.y && int64(U.y) < minYUp {
					minYUp = int64(U.y)
					minYUpID = uIdx
				}
				if U.y < v.y && int64(U.y) > maxYDown {
					maxYDown = int64(U.y)
					maxYDownID = uIdx
				}
			}

			yUp := math.Inf(1)
			var upPc float64
			if segUp != nil {
				num, den := evalY(segUp, int64(X))
				yUp = float64(num) / float64(den)
				dx := float64(X) - float64(segUp.OrigA.x)
				dy := yUp - float64(segUp.OrigA.y)
				upPc = perimeterPrefix[segUp.id] + math.Hypot(dx, dy)
			}
			if minYUp != math.MaxInt64 {
				yVert := float64(minYUp)
				if yVert < yUp {
					yUp = yVert
					upPc = perimeterPrefix[minYUpID]
				}
			}
			if !math.IsInf(yUp, 1) {
				Vprev := V[(vIdx-1+n)%n]
				Vnext := V[(vIdx+1)%n]
				if strictlyInsideUp(v, Vprev, Vnext) {
					descends = append(descends, Descend{
						fromPc: upPc,
						toPc:   perimeterPrefix[vIdx],
						weight: yUp - float64(v.y),
					})
				}
			}

			yDown := math.Inf(-1)
			var downPc float64
			if segDown != nil {
				num, den := evalY(segDown, int64(X))
				yDown = float64(num) / float64(den)
				dx := float64(X) - float64(segDown.OrigA.x)
				dy := yDown - float64(segDown.OrigA.y)
				downPc = perimeterPrefix[segDown.id] + math.Hypot(dx, dy)
			}
			if maxYDown != math.MinInt64 {
				yVert := float64(maxYDown)
				if yVert > yDown {
					yDown = yVert
					downPc = perimeterPrefix[maxYDownID]
				}
			}
			if !math.IsInf(yDown, -1) {
				Vprev := V[(vIdx-1+n)%n]
				Vnext := V[(vIdx+1)%n]
				if strictlyInsideDown(v, Vprev, Vnext) {
					descends = append(descends, Descend{
						fromPc: perimeterPrefix[vIdx],
						toPc:   downPc,
						weight: float64(v.y) - yDown,
					})
				}
			}
		}

		for _, seg := range ev.starts {
			root = insert(root, seg, int64(X))
		}
	}

	var pcList []float64
	pcList = append(pcList, perimeterPrefix[sIdx], perimeterPrefix[tIdx])
	for _, d := range descends {
		pcList = append(pcList, d.fromPc, d.toPc)
	}

	for i := range pcList {
		if pcList[i] >= L-1e-7 {
			pcList[i] = 0
		}
	}
	sort.Float64s(pcList)

	var nodes []float64
	for _, pc := range pcList {
		if len(nodes) == 0 || pc-nodes[len(nodes)-1] > 1e-7 {
			nodes = append(nodes, pc)
		}
	}

	getID := func(pc float64) int {
		if pc >= L-1e-7 {
			pc = 0
		}
		idx := sort.Search(len(nodes), func(i int) bool {
			return nodes[i] >= pc-1e-7
		})
		if idx < len(nodes) && math.Abs(nodes[idx]-pc) <= 1e-7 {
			return idx
		}
		if idx > 0 && math.Abs(nodes[idx-1]-pc) <= 1e-7 {
			return idx - 1
		}
		return -1
	}

	graph := make([][]Edge, len(nodes))
	for i := 0; i < len(nodes); i++ {
		next := (i + 1) % len(nodes)
		w := nodes[next] - nodes[i]
		if w < 0 {
			w += L
		}
		graph[i] = append(graph[i], Edge{next, w})
		graph[next] = append(graph[next], Edge{i, w})
	}

	for _, d := range descends {
		u := getID(d.fromPc)
		v := getID(d.toPc)
		if u != v && u != -1 && v != -1 {
			graph[u] = append(graph[u], Edge{v, d.weight})
		}
	}

	dist := make([]float64, len(nodes))
	for i := range dist {
		dist[i] = math.Inf(1)
	}

	startNode := getID(perimeterPrefix[sIdx])
	targetNode := getID(perimeterPrefix[tIdx])

	dist[startNode] = 0
	pq := make(PriorityQueue, 0)
	heap.Push(&pq, &PQItem{node: startNode, dist: 0})

	for pq.Len() > 0 {
		curr := heap.Pop(&pq).(*PQItem)
		u := curr.node
		if curr.dist > dist[u] {
			continue
		}
		if u == targetNode {
			break
		}
		for _, edge := range graph[u] {
			if dist[u]+edge.w < dist[edge.to] {
				dist[edge.to] = dist[u] + edge.w
				heap.Push(&pq, &PQItem{node: edge.to, dist: dist[edge.to]})
			}
		}
	}

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