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