For problem statement at 0-999/900-999/930-939/933/problemC.txt this is a correct solution, but verifier at 0-999/900-999/930-939/933/verifierC.go ends with All tests passed can you fix the verifier? package main
import (
"bufio"
"fmt"
"math"
"os"
)
type Circle struct {
x, y, r int
}
type Point struct {
x, y float64
}
type DSU struct {
p, r []int
}
func NewDSU(n int) *DSU {
p := make([]int, n)
r := make([]int, n)
for i := 0; i < n; i++ {
p[i] = i
}
return &DSU{p: p, r: r}
}
func (d *DSU) Find(x int) int {
if d.p[x] != x {
d.p[x] = d.Find(d.p[x])
}
return d.p[x]
}
func (d *DSU) Union(a, b int) {
ra, rb := d.Find(a), d.Find(b)
if ra == rb {
return
}
if d.r[ra] < d.r[rb] {
ra, rb = rb, ra
}
d.p[rb] = ra
if d.r[ra] == d.r[rb] {
d.r[ra]++
}
}
func pairCount(a, b Circle) int {
dx := a.x - b.x
dy := a.y - b.y
d2 := dx*dx + dy*dy
sum := a.r + b.r
diff := a.r - b.r
if diff < 0 {
diff = -diff
}
if d2 > sum*sum || d2 < diff*diff {
return 0
}
if d2 == sum*sum || d2 == diff*diff {
return 1
}
return 2
}
func interPoints(a, b Circle, cnt int) []Point {
x1, y1, r1 := float64(a.x), float64(a.y), float64(a.r)
x2, y2, r2 := float64(b.x), float64(b.y), float64(b.r)
dx := x2 - x1
dy := y2 - y1
d := math.Hypot(dx, dy)
ad := (r1*r1 - r2*r2 + d*d) / (2 * d)
mx := x1 + ad*dx/d
my := y1 + ad*dy/d
if cnt == 1 {
return []Point{{mx, my}}
}
h2 := r1*r1 - ad*ad
if h2 < 0 && h2 > -1e-12 {
h2 = 0
}
h := math.Sqrt(h2)
rx := -dy * h / d
ry := dx * h / d
return []Point{{mx + rx, my + ry}, {mx - rx, my - ry}}
}
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int
if _, err := fmt.Fscan(in, &n); err != nil {
return
}
circles := make([]Circle, n)
for i := 0; i < n; i++ {
fmt.Fscan(in, &circles[i].x, &circles[i].y, &circles[i].r)
}
var cnt [3][3]int
totalPair := 0
dsu := NewDSU(n)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
c := pairCount(circles[i], circles[j])
cnt[i][j], cnt[j][i] = c, c
totalPair += c
if c > 0 {
dsu.Union(i, j)
}
}
}
t := 0
if n == 3 {
bi, bj, bc := -1, -1, 0
for i := 0; i < 3; i++ {
for j := i + 1; j < 3; j++ {
if cnt[i][j] > bc {
bc = cnt[i][j]
bi, bj = i, j
}
}
}
if bc > 0 {
pts := interPoints(circles[bi], circles[bj], bc)
k := 3 - bi - bj
cx, cy := float64(circles[k].x), float64(circles[k].y)
rr := float64(circles[k].r * circles[k].r)
for _, p := range pts {
dx := p.x - cx
dy := p.y - cy
if math.Abs(dx*dx+dy*dy-rr) <= 1e-7 {
t++
}
}
}
}
kcnt := make([]int, n)
for i := 0; i < n; i++ {
s := 0
for j := 0; j < n; j++ {
s += cnt[i][j]
}
kcnt[i] = s - t
}
z := 0
E := 0
for i := 0; i < n; i++ {
if kcnt[i] == 0 {
z++
E++
} else {
E += kcnt[i]
}
}
V := totalPair - 2*t
Vp := V + z
roots := make(map[int]bool)
for i := 0; i < n; i++ {
roots[dsu.Find(i)] = true
}
C := len(roots)
F := E - Vp + C + 1
fmt.Fprintln(out, F)
}