For problem statement at 1000-1999/1300-1399/1350-1359/1359/problemF.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1350-1359/1359/verifierF.go ends with case 16 mismatch
expected:No show :(
got:0.000000000005082
input:10
0 3 3 -6 1
7 4 8 -5 1
-2 -5 -4 2 4
3 5 -2 -9 7
7 4 3 -5 3
-1 0 1 6 6
7 5 -4 8 5
4 -8 -4 4 10
5 -7 -8 3 3
-6 6 5 7 1
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
)
type FastScanner struct {
r *bufio.Reader
}
func NewFastScanner() *FastScanner {
return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}
func (fs *FastScanner) NextInt() int64 {
sign := int64(1)
val := int64(0)
c, _ := fs.r.ReadByte()
for (c < '0' || c > '9') && c != '-' {
c, _ = fs.r.ReadByte()
}
if c == '-' {
sign = -1
c, _ = fs.r.ReadByte()
}
for c >= '0' && c <= '9' {
val = val*10 + int64(c-'0')
c, _ = fs.r.ReadByte()
}
fs.r.UnreadByte()
return val * sign
}
type Car struct {
x, y int64
dx, dy int64
s int64
xf, yf float64
slope float64
intercept float64
reach float64
vx, vy float64
}
type TempSeg struct {
lim float64
leftX, rightX float64
}
type Event struct {
x, y float64
typ int
id int
}
type Node struct {
id int
pr uint32
left, right *Node
}
var (
n int
cars []Car
segs []TempSeg
events []Event
nodes []Node
curX float64
seed uint32 = 2463534242
)
func rnd() uint32 {
seed ^= seed << 13
seed ^= seed >> 17
seed ^= seed << 5
return seed
}
func yAt(id int, x float64) float64 {
c := cars[id]
return c.slope*x + c.intercept
}
func less(i, j int) bool {
if i == j {
return false
}
ci := cars[i]
cj := cars[j]
yi := ci.slope*curX + ci.intercept
yj := cj.slope*curX + cj.intercept
if yi < yj {
return true
}
if yi > yj {
return false
}
if ci.slope < cj.slope {
return true
}
if ci.slope > cj.slope {
return false
}
if ci.intercept < cj.intercept {
return true
}
if ci.intercept > cj.intercept {
return false
}
return i < j
}
func rotateRight(p *Node) *Node {
q := p.left
p.left = q.right
q.right = p
return q
}
func rotateLeft(p *Node) *Node {
q := p.right
p.right = q.left
q.left = p
return q
}
func insert(root *Node, node *Node) *Node {
if root == nil {
return node
}
if less(node.id, root.id) {
root.left = insert(root.left, node)
if root.left.pr < root.pr {
root = rotateRight(root)
}
} else {
root.right = insert(root.right, node)
if root.right.pr < root.pr {
root = rotateLeft(root)
}
}
return root
}
func merge(a, b *Node) *Node {
if a == nil {
return b
}
if b == nil {
return a
}
if a.pr < b.pr {
a.right = merge(a.right, b)
return a
}
b.left = merge(a, b.left)
return b
}
func erase(root *Node, id int) *Node {
if root == nil {
return nil
}
if root.id == id {
return merge(root.left, root.right)
}
if less(id, root.id) {
root.left = erase(root.left, id)
} else {
root.right = erase(root.right, id)
}
return root
}
func minNode(root *Node) int {
for root.left != nil {
root = root.left
}
return root.id
}
func maxNode(root *Node) int {
for root.right != nil {
root = root.right
}
return root.id
}
func findPredSucc(root *Node, id int) (int, int) {
pred, succ := -1, -1
cur := root
for cur != nil {
if less(id, cur.id) {
succ = cur.id
cur = cur.left
} else if less(cur.id, id) {
pred = cur.id
cur = cur.right
} else {
if cur.left != nil {
pred = maxNode(cur.left)
}
if cur.right != nil {
succ = minNode(cur.right)
}
break
}
}
return pred, succ
}
func intersects(i, j int) bool {
ci := cars[i]
cj := cars[j]
den := ci.dx*cj.dy - ci.dy*cj.dx
diffx := cj.x - ci.x
diffy := cj.y - ci.y
if den != 0 {
numT := diffx*cj.dy - diffy*cj.dx
numU := diffx*ci.dy - diffy*ci.dx
if den < 0 {
den = -den
numT = -numT
numU = -numU
}
if numT < 0 || numU < 0 {
return false
}
t := float64(numT) / float64(den)
u := float64(numU) / float64(den)
limI := segs[i].lim
limJ := segs[j].lim
epsI := 1e-12 * math.Max(1.0, math.Max(t, limI))
epsJ := 1e-12 * math.Max(1.0, math.Max(u, limJ))
return t <= limI+epsI && u <= limJ+epsJ
}
if diffx*ci.dy-diffy*ci.dx != 0 {
return false
}
l := segs[i].leftX
if segs[j].leftX > l {
l = segs[j].leftX
}
r := segs[i].rightX
if segs[j].rightX < r {
r = segs[j].rightX
}
return l <= r+1e-9
}
func feasible(T float64) bool {
if T <= 0 {
return false
}
m := 2 * n
for i := 0; i < n; i++ {
c := cars[i]
lim := c.reach * T
qx := c.xf + c.vx*T
qy := c.yf + c.vy*T
if qx < c.xf {
segs[i].lim = lim
segs[i].leftX = qx
segs[i].rightX = c.xf
events[2*i] = Event{x: qx, y: qy, typ: 0, id: i}
events[2*i+1] = Event{x: c.xf, y: c.yf, typ: 1, id: i}
} else {
segs[i].lim = lim
segs[i].leftX = c.xf
segs[i].rightX = qx
events[2*i] = Event{x: c.xf, y: c.yf, typ: 0, id: i}
events[2*i+1] = Event{x: qx, y: qy, typ: 1, id: i}
}
nodes[i].left = nil
nodes[i].right = nil
}
sort.Slice(events[:m], func(a, b int) bool {
e1 := events[a]
e2 := events[b]
if e1.x < e2.x {
return true
}
if e1.x > e2.x {
return false
}
if e1.y < e2.y {
return true
}
if e1.y > e2.y {
return false
}
if e1.typ < e2.typ {
return true
}
if e1.typ > e2.typ {
return false
}
return e1.id < e2.id
})
var root *Node
starts := make([]int, 0, n)
ends := make([]int, 0, n)
for l := 0; l < m; {
r := l + 1
x := events[l].x
for r < m && events[r].x == x {
r++
}
starts = starts[:0]
ends = ends[:0]
for k := l; k < r; k++ {
if events[k].typ == 0 {
starts = append(starts, events[k].id)
} else {
ends = append(ends, events[k].id)
}
}
curX = math.Nextafter(x, math.Inf(-1))
for _, id := range starts {
pred, succ := findPredSucc(root, id)
if pred != -1 && intersects(id, pred) {
return true
}
if succ != -1 && intersects(id, succ) {
return true
}
}
for _, id := range ends {
pred, succ := findPredSucc(root, id)
if pred != -1 && intersects(id, pred) {
return true
}
if succ != -1 && intersects(id, succ) {
return true
}
root = erase(root, id)
if pred != -1 && succ != -1 && intersects(pred, succ) {
return true
}
}
curX = math.Nextafter(x, math.Inf(1))
for _, id := range starts {
pred, succ := findPredSucc(root, id)
root = insert(root, &nodes[id])
if pred != -1 && intersects(id, pred) {
return true
}
if succ != -1 && intersects(id, succ) {
return true
}
}
l = r
}
return false
}
func main() {
in := NewFastScanner()
n64 := in.NextInt()
n = int(n64)
if n < 2 {
fmt.Println("No show :(")
return
}
cars = make([]Car, n)
segs = make([]TempSeg, n)
events = make([]Event, 2*n)
nodes = make([]Node, n)
for i := 0; i < n; i++ {
x := in.NextInt()
y := in.NextInt()
dx := in.NextInt()
dy := in.NextInt()
s := in.NextInt()
lenv := math.Hypot(float64(dx), float64(dy))
slope := float64(dy) / float64(dx)
xf := float64(x)
yf := float64(y)
reach := float64(s) / lenv
vx := float64(dx) * reach
vy := float64(dy) * reach
cars[i] = Car{
x: x,
y: y,
dx: dx,
dy: dy,
s: s,
xf: xf,
yf: yf,
slope: slope,
intercept: yf - slope*xf,
reach: reach,
vx: vx,
vy: vy,
}
nodes[i].id = i
nodes[i].pr = rnd()
}
const HI = 6000000000.0
if !feasible(HI) {
fmt.Println("No show :(")
return
}
lo, hi := 0.0, HI
for it := 0; it < 70; it++ {
mid := (lo + hi) * 0.5
if feasible(mid) {
hi = mid
} else {
lo = mid
}
}
out := bufio.NewWriterSize(os.Stdout, 1<<20)
fmt.Fprintf(out, "%.15f\n", hi)
out.Flush()
}