For problem statement at 1000-1999/1500-1599/1570-1579/1575/problemB.txt this is a correct solution, but verifier at 1000-1999/1500-1599/1570-1579/1575/verifierB.go ends with test 1 failed:
input:
5 2
0 -5
-5 4
-2 -5
-2 -2
-4 4
expected: 2.50001382731227
got: 2.500000
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
)
type Event struct {
pos float64
val int
}
type EventSlice []Event
func (s EventSlice) Len() int { return len(s) }
func (s EventSlice) Less(i, j int) bool {
if s[i].pos != s[j].pos {
return s[i].pos < s[j].pos
}
return s[i].val > s[j].val
}
func (s EventSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func main() {
in := bufio.NewReader(os.Stdin)
var n, k int
if _, err := fmt.Fscan(in, &n, &k); err != nil {
return
}
type Point struct {
d float64
alpha float64
}
originCount := 0
pts := make([]Point, 0, n)
for i := 0; i < n; i++ {
var x, y float64
fmt.Fscan(in, &x, &y)
if x == 0 && y == 0 {
originCount++
} else {
pts = append(pts, Point{
d: math.Hypot(x, y),
alpha: math.Atan2(y, x),
})
}
}
k -= originCount
if k <= 0 {
fmt.Printf("%.5f\n", 0.0)
return
}
events := make(EventSlice, 0, 4*len(pts))
check := func(r float64) bool {
events = events[:0]
for _, p := range pts {
if p.d > 2*r {
continue
}
ratio := p.d / (2 * r)
if ratio > 1.0 {
ratio = 1.0
}
delta := math.Acos(ratio) + 1e-11
l := p.alpha - delta
ri := p.alpha + delta
events = append(events, Event{l, 1}, Event{ri, -1}, Event{l + 2*math.Pi, 1}, Event{ri + 2*math.Pi, -1})
}
sort.Sort(events)
cnt := 0
maxCnt := 0
for _, e := range events {
cnt += e.val
if cnt > maxCnt {
maxCnt = cnt
}
}
return maxCnt >= k
}
low, high := 0.0, 3e5
for iter := 0; iter < 55; iter++ {
mid := (low + high) / 2
if check(mid) {
high = mid
} else {
low = mid
}
}
fmt.Printf("%.6f\n", high)
}