```go
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
// Use buffered I/O for speed
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
if !scanner.Scan() {
return
}
n := parseInt(scanner.Bytes())
// Read grid
grid := make([][]int8, n)
for i := 0; i < n; i++ {
grid[i] = make([]int8, n)
for j := 0; j < n; j++ {
scanner.Scan()
b := scanner.Bytes()
if len(b) > 0 && b[0] == '1' {
grid[i][j] = 1
}
}
}
// Calculate Prefix Sums (Integral Image) for fast local averaging
sum := make([][]int, n+1)
for i := 0; i < n+1; i++ {
sum[i] = make([]int, n+1)
}
for i := 0; i < n; i++ {
rowSum := 0
for j := 0; j < n; j++ {
rowSum += int(grid[i][j])
sum[i+1][j+1] = sum[i][j+1] + rowSum
}
}
visited := make([][]bool, n)
for i := range visited {
visited[i] = make([]bool, n)
}
circles := 0
squares := 0
// Queue for BFS, reused to hold component pixels
q := make([][2]int, 0, n*n)
dys := []int{-1, 1, 0, 0}
dxs := []int{0, 0, -1, 1}
// Iterate over the grid to find components
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if visited[i][j] {
continue
}
// Apply 5x5 box filter (smoothing) to handle noise
// Check if current pixel neighborhood has enough black pixels
rMin := i - 2
if rMin < 0 {
rMin = 0
}
rMax := i + 2
if rMax >= n {
rMax = n - 1
}
cMin := j - 2
if cMin < 0 {
cMin = 0
}
cMax := j + 2
if cMax >= n {
cMax = n - 1
}
// Calculate sum in window
val := sum[rMax+1][cMax+1] - sum[rMin][cMax+1] - sum[rMax+1][cMin] + sum[rMin][cMin]
// Threshold: 13 out of 25 pixels (approx 50%) separates 20% noise from object
if val < 13 {
continue
}
// BFS to find connected component on the smoothed image
visited[i][j] = true
q = q[:0]
q = append(q, [2]int{i, j})
head := 0
for head < len(q) {
curr := q[head]
head++
cy, cx := curr[0], curr[1]
for k := 0; k < 4; k++ {
ny, nx := cy+dys[k], cx+dxs[k]
if ny >= 0 && ny < n && nx >= 0 && nx < n && !visited[ny][nx] {
// Check neighbor's smoothed value
nrMin := ny - 2
if nrMin < 0 {
nrMin = 0
}
nrMax := ny + 2
if nrMax >= n {
nrMax = n - 1
}
ncMin := nx - 2
if ncMin < 0 {
ncMin = 0
}
ncMax := nx + 2
if ncMax >= n {
ncMax = n - 1
}
sVal := sum[nrMax+1][ncMax+1] - sum[nrMin][ncMax+1] - sum[nrMax+1][ncMin] + sum[nrMin][ncMin]
if sVal >= 13 {
visited[ny][nx] = true
q = append(q, [2]int{ny, nx})
}
}
}
}
// Filter small components (noise artifacts)
// Shapes are at least size 15 (~225 area). Eroded area > 120 is safe.
if len(q) > 120 {
if solve(q) == 1 {
circles++
} else {
squares++
}
}
}
}
fmt.Println(circles, squares)
}
func parseInt(b []byte) int {
res := 0
for _, c := range b {
res = res*10 + int(c-'0')
}
return res
}
// Classify component as Circle (1) or Square (2)
func solve(pts [][2]int) int {
sumY, sumX := 0, 0
for _, p := range pts {
sumY += p[0]
sumX += p[1]
}
count := float64(len(pts))
cY := float64(sumY) / count
cX := float64(sumX) / count
maxDistSq := 0.0
for _, p := range pts {
dy := float64(p[0]) - cY
dx := float64(p[1]) - cX
d2 := dy*dy + dx*dx
if d2 > maxDistSq {
maxDistSq = d2
}
}
if maxDistSq == 0 {
return 2
}
// Metric: Area / (MaxDistance^2)
// For Circle: Area = Pi*R^2, MaxDist = R. Ratio ~ 3.14
// For Square: Area = a^2, MaxDist = a/sqrt(2). Ratio = a^2 / (a^2/2) = 2.0
// Smoothing erodes corners of squares, raising the ratio slightly (e.g. to 2.3).
// Threshold of 2.6 reliably separates them.
ratio := count / maxDistSq
if ratio > 2.6 {
return 1
}
return 2
}
```