For problem statement at 1000-1999/1500-1599/1510-1519/1510/problemF.txt this is a correct solution, but verifier at 1000-1999/1500-1599/1510-1519/1510/verifierF.go ends with test 1 mismatch: expected 0.845616557381 got 3.012712585980
input:
3 4.000000
0.000000 0.000000
1.000000 0.000000
0.000000 1.000000
reference output:
0.845616557380924
participant output:
3.012712585980356
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
)
type Point struct {
x, y float64
}
type Ray struct {
angle float64
orig Point
dir Point
}
type Sector struct {
F1 Point
F2 Point
L_hidden float64
}
func main() {
reader := bufio.NewReader(os.Stdin)
var n int
var L float64
if _, err := fmt.Fscanf(reader, "%d %f\n", &n, &L); err != nil {
return
}
V := make([]Point, n)
for i := 0; i < n; i++ {
fmt.Fscanf(reader, "%f %f\n", &V[i].x, &V[i].y)
}
pref := make([]float64, n)
cur := 0.0
for i := 0; i < n; i++ {
pref[i] = cur
p1 := V[i]
p2 := V[(i+1)%n]
cur += math.Hypot(p1.x-p2.x, p1.y-p2.y)
}
P_poly := cur
ccwDist := func(i, j int) float64 {
d := pref[j] - pref[i]
if d < 0 {
d += P_poly
}
return d
}
rays := make([]Ray, 0, 2*n)
for i := 0; i < n; i++ {
p1 := V[i]
p2 := V[(i+1)%n]
E := Point{p2.x - p1.x, p2.y - p1.y}
LE := math.Hypot(E.x, E.y)
U := Point{E.x / LE, E.y / LE}
angFwd := math.Atan2(U.y, U.x)
if angFwd < 0 {
angFwd += 2 * math.Pi
}
rays = append(rays, Ray{angle: angFwd, orig: p2, dir: U})
Ubwd := Point{-U.x, -U.y}
angBwd := math.Atan2(Ubwd.y, Ubwd.x)
if angBwd < 0 {
angBwd += 2 * math.Pi
}
rays = append(rays, Ray{angle: angBwd, orig: p1, dir: Ubwd})
}
sort.Slice(rays, func(i, j int) bool {
return rays[i].angle < rays[j].angle
})
sectors := make([]Sector, 2*n)
for k := 0; k < 2*n; k++ {
ang1 := rays[k].angle
ang2 := rays[(k+1)%(2*n)].angle
if k == 2*n-1 {
ang2 += 2 * math.Pi
}
mid := (ang1 + ang2) / 2.0
ux := math.Cos(mid)
uy := math.Sin(mid)
maxVal := -1e18
minVal := 1e18
idxLeft := -1
idxRight := -1
for i, p := range V {
val := -uy*p.x + ux*p.y
if val > maxVal {
maxVal = val
idxLeft = i
}
if val < minVal {
minVal = val
idxRight = i
}
}
sectors[k] = Sector{
F1: V[idxLeft],
F2: V[idxRight],
L_hidden: ccwDist(idxLeft, idxRight),
}
}
Pk := make([]Point, 2*n)
for k := 0; k < 2*n; k++ {
sec := sectors[k]
F1 := sec.F1
F2 := sec.F2
D := L - sec.L_hidden
Vorig := rays[k].orig
U := rays[k].dir
A := Point{Vorig.x - F1.x, Vorig.y - F1.y}
B := Point{Vorig.x - F2.x, Vorig.y - F2.y}
P := 2.0 * (U.x*(A.x-B.x) + U.y*(A.y-B.y))
Q := (A.x*A.x + A.y*A.y) - (B.x*B.x + B.y*B.y) - D*D
a_quad := P*P - 4.0*D*D
b_quad := 2.0*P*Q - 8.0*D*D*(U.x*B.x+U.y*B.y)
c_quad := Q*Q - 4.0*D*D*(B.x*B.x+B.y*B.y)
disc := b_quad*b_quad - 4.0*a_quad*c_quad
if disc < 0 {
disc = 0
}
r := (-b_quad - math.Sqrt(disc)) / (2.0 * a_quad)
Pk[k] = Point{Vorig.x + r*U.x, Vorig.y + r*U.y}
}
totalArea := 0.0
for k := 0; k < 2*n; k++ {
sec := sectors[k]
F1 := sec.F1
F2 := sec.F2
D := L - sec.L_hidden
a_el := D / 2.0
dxF := F1.x - F2.x
dyF := F1.y - F2.y
distF := math.Hypot(dxF, dyF)
c_el := distF / 2.0
b_el := math.Sqrt(math.Max(0, a_el*a_el-c_el*c_el))
C := Point{(F1.x + F2.x) / 2.0, (F1.y + F2.y) / 2.0}
var Uel, Vel Point
if distF < 1e-9 {
Uel = Point{1.0, 0.0}
} else {
Uel = Point{dxF / distF, dyF / distF}
}
Vel = Point{-Uel.y, Uel.x}
pStart := Pk[k]
pEnd := Pk[(k+1)%(2*n)]
dx0 := pStart.x - C.x
dy0 := pStart.y - C.y
cos0 := (dx0*Uel.x + dy0*Uel.y) / a_el
sin0 := (dx0*Vel.x + dy0*Vel.y) / b_el
t0 := math.Atan2(sin0, cos0)
dx1 := pEnd.x - C.x
dy1 := pEnd.y - C.y
cos1 := (dx1*Uel.x + dy1*Uel.y) / a_el
sin1 := (dx1*Vel.x + dy1*Vel.y) / b_el
t1 := math.Atan2(sin1, cos1)
diff := t1 - t0
for diff < 0 {
diff += 2.0 * math.Pi
}
for diff >= 2.0*math.Pi {
diff -= 2.0 * math.Pi
}
term1 := a_el * b_el * diff
term2 := a_el * (math.Cos(t1) - math.Cos(t0)) * (C.x*Uel.y - C.y*Uel.x)
term3 := b_el * (math.Sin(t1) - math.Sin(t0)) * (C.x*Vel.y - C.y*Vel.x)
totalArea += 0.5 * (term1 + term2 + term3)
}
fmt.Printf("%.15f\n", totalArea)
}