For problem statement at 0-999/0-99/40-49/47/problemE.txt this is a correct solution, but verifier at 0-999/0-99/40-49/47/verifierE.go ends with test 1 failed. Expected:
1.188513 0.000000
4.595913 0.000000
Got:
1.1885131321 0.0000000000
4.5959131458 0.0000000000
exit status 1 can you fix the verifier? package main
import (
"bufio"
"container/heap"
"fmt"
"math"
"os"
"sort"
)
type Event struct {
k float64
typ int // 0=start, 1=query, 2=end
id int
}
type Item struct {
xi float64
id int
}
type MinHeap []Item
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].xi < h[j].xi || (h[i].xi == h[j].xi && h[i].id < h[j].id) }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
it := old[n-1]
*h = old[:n-1]
return it
}
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
const g = 9.8
const eps = 1e-12
var n int
var V float64
if _, err := fmt.Fscan(in, &n, &V); err != nil {
return
}
alphas := make([]float64, n)
for i := 0; i < n; i++ {
fmt.Fscan(in, &alphas[i])
}
var m int
fmt.Fscan(in, &m)
type key int64
wallMap := make(map[key]float64)
for i := 0; i < m; i++ {
var xf, yf float64
fmt.Fscan(in, &xf, &yf)
xk := key(int64(math.Round(xf * 10000.0)))
if cur, ok := wallMap[xk]; !ok || yf > cur {
wallMap[xk] = yf
}
}
// Build walls arrays
W := len(wallMap)
wallX := make([]float64, 0, W)
wallH := make([]float64, 0, W)
for k, h := range wallMap {
x := float64(k) / 10000.0
wallX = append(wallX, x)
wallH = append(wallH, h)
}
W = len(wallX)
events := make([]Event, 0, 2*W+n)
active := make([]bool, W)
// Build intervals for walls
V2 := V * V
for id := 0; id < W; id++ {
x := wallX[id]
H := wallH[id]
u := g * x / V2
if u > 1.0+eps {
continue
}
if u <= 0 {
continue
}
s := math.Sqrt(math.Max(0, 1.0-u*u))
kLower := (1.0 - s) / u
if kLower < 0 {
kLower = 0
}
if kLower > 1 {
continue
}
A := g * x * x / (2.0 * V2)
D := x*x - 4.0*A*(A+H)
var r float64
if D <= eps {
r = 1.0
} else {
sq := math.Sqrt(D)
r1 := (x - sq) / (2.0 * A)
if r1 >= 1.0-eps {
r = 1.0
} else {
r = r1
}
}
if r < kLower-eps {
continue
}
if r > 1.0 {
r = 1.0
}
if r < 0 {
continue
}
events = append(events, Event{k: kLower, typ: 0, id: id})
events = append(events, Event{k: r, typ: 2, id: id})
}
// Build query events
ansX := make([]float64, n)
ansY := make([]float64, n)
for i := 0; i < n; i++ {
k := math.Tan(alphas[i])
events = append(events, Event{k: k, typ: 1, id: i})
// default ground landing
ansX[i] = V2 * math.Sin(2.0*alphas[i]) / g
ansY[i] = 0.0
}
sort.Slice(events, func(i, j int) bool {
if events[i].k != events[j].k {
return events[i].k < events[j].k
}
return events[i].typ < events[j].typ
})
hp := &MinHeap{}
heap.Init(hp)
for _, ev := range events {
if ev.typ == 0 {
active[ev.id] = true
heap.Push(hp, Item{xi: wallX[ev.id], id: ev.id})
} else if ev.typ == 2 {
active[ev.id] = false
} else {
qid := ev.id
k := math.Tan(alphas[qid])
for hp.Len() > 0 {
top := (*hp)[0]
if active[top.id] {
break
}
heap.Pop(hp)
}
if hp.Len() == 0 {
continue
}
top := (*hp)[0]
x := top.xi
A := g * x * x / (2.0 * V2)
y := x*k - A*(1.0+k*k)
if y < 0 {
y = 0
}
ansX[qid] = x
ansY[qid] = y
}
}
for i := 0; i < n; i++ {
fmt.Fprintf(out, "%.10f %.10f\n", ansX[i], ansY[i])
}
}