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])
}
```