For problem statement at 0-999/400-499/410-419/419/problemE.txt this is a correct solution, but verifier at 0-999/400-499/410-419/419/verifierE.go ends with case 1 failed: expected 4 got 2
input:
1 5
-7 4 5
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
)
type Event struct {
angle float64
delta int
}
func main() {
reader := bufio.NewReader(os.Stdin)
var n int
var d float64
if _, err := fmt.Fscan(reader, &n, &d); err != nil {
return
}
var events []Event
for i := 0; i < n; i++ {
var x, y, r float64
fmt.Fscan(reader, &x, &y, &r)
D := math.Hypot(x, y)
theta := math.Atan2(y, x)
if theta < 0 {
theta += 2 * math.Pi
}
kmin := int(math.Floor((D-r)/d)) - 1
if kmin < 1 {
kmin = 1
}
kmax := int(math.Ceil((D+r)/d)) + 1
for k := kmin; k <= kmax; k++ {
kd := float64(k) * d
if kd < D-r-1e-7 || kd > D+r+1e-7 {
continue
}
V := (kd*kd + D*D - r*r) / (2 * kd * D)
if V > 1.0 {
V = 1.0
} else if V < -1.0 {
V = -1.0
}
delta := math.Acos(V)
L := theta - delta
R := theta + delta
if L < 0 {
events = append(events, Event{L + 2*math.Pi, 1}, Event{2 * math.Pi, -1})
events = append(events, Event{0, 1}, Event{R, -1})
} else if R >= 2*math.Pi {
events = append(events, Event{L, 1}, Event{2 * math.Pi, -1})
events = append(events, Event{0, 1}, Event{R - 2*math.Pi, -1})
} else {
events = append(events, Event{L, 1}, Event{R, -1})
}
}
}
sort.Slice(events, func(i, j int) bool {
if math.Abs(events[i].angle-events[j].angle) > 1e-11 {
return events[i].angle < events[j].angle
}
return events[i].delta > events[j].delta
})
maxOverlap := 0
currentOverlap := 0
for _, e := range events {
currentOverlap += e.delta
if currentOverlap > maxOverlap {
maxOverlap = currentOverlap
}
}
fmt.Println(maxOverlap)
}