← Home
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)
}