For problem statement at 0-999/0-99/60-69/68/problemE.txt this is a correct solution, but verifier at 0-999/0-99/60-69/68/verifierE.go ends with build oracle failed: exit status 1
# command-line-arguments
./68E.go:106:16: undefined: chooseVerts
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
"strconv"
)
type Triangle struct {
d [3][3]int
key [3]int
}
type Point struct {
x float64
y float64
}
var tris [4]Triangle
var edgeLen [12][12]int
var best int
var memo [5]map[string]bool
func main() {
in := bufio.NewReader(os.Stdin)
for i := 0; i < 4; i++ {
var x [3]int
var y [3]int
fmt.Fscan(in, &x[0], &y[0], &x[1], &y[1], &x[2], &y[2])
var t Triangle
for a := 0; a < 3; a++ {
for b := a + 1; b < 3; b++ {
dx := x[a] - x[b]
dy := y[a] - y[b]
v := dx*dx + dy*dy
t.d[a][b] = v
t.d[b][a] = v
}
}
k := []int{t.d[0][1], t.d[0][2], t.d[1][2]}
sort.Ints(k)
t.key = [3]int{k[0], k[1], k[2]}
tris[i] = t
}
sort.Slice(tris[:], func(i, j int) bool {
for k := 0; k < 3; k++ {
if tris[i].key[k] != tris[j].key[k] {
return tris[i].key[k] < tris[j].key[k]
}
}
return false
})
for i := 0; i < 12; i++ {
for j := 0; j < 12; j++ {
edgeLen[i][j] = -1
}
}
edgeLen[0][1] = tris[0].d[0][1]
edgeLen[1][0] = tris[0].d[0][1]
edgeLen[0][2] = tris[0].d[0][2]
edgeLen[2][0] = tris[0].d[0][2]
edgeLen[1][2] = tris[0].d[1][2]
edgeLen[2][1] = tris[0].d[1][2]
best = 12
search(1, 3)
fmt.Println(best)
}
func search(idx, n int) {
if n >= best || best == 3 {
return
}
sig := makeSig(idx, n)
if memo[idx] == nil {
memo[idx] = make(map[string]bool)
}
if memo[idx][sig] {
return
}
memo[idx][sig] = true
if idx == 4 {
if isRealizable(n) {
best = n
}
return
}
var mp [3]int
assignTriangle(idx, 0, n, 0, &mp)
}
func assignTriangle(ti, pos, n, newUsed int, mp *[3]int) {
if n+newUsed >= best {
return
}
if pos == 3 {
search(ti+1, n+newUsed)
return
}
maxID := n + newUsed
for g := 0; g <= maxID; g++ {
ok := true
for i := 0; i < pos; i++ {
if mp[i] == g {
ok = false
break
}
}
if !ok {
continue
}
added := make([][2]int, 0, 3)
for i := 0; i < pos; i++ {
a, b := g, mp[i]
need := tris[ti].d[pos][i]
if edgeLen[a][b] == -1 {
edgeLen[a][b] = need
edgeLen[b][a] = need
added = append(added, [2]int{a, b})
} else if edgeLen[a][b] != need {
ok = false
break
}
}
if ok {
mp[pos] = g
nu := newUsed
if g == maxID {
nu++
}
assignTriangle(ti, pos+1, n, nu, mp)
}
for _, p := range added {
edgeLen[p[0]][p[1]] = -1
edgeLen[p[1]][p[0]] = -1
}
}
}
func makeSig(idx, n int) string {
buf := make([]byte, 0, 300)
buf = strconv.AppendInt(buf, int64(idx), 10)
buf = append(buf, '|')
buf = strconv.AppendInt(buf, int64(n), 10)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
buf = append(buf, ',')
if edgeLen[i][j] == -1 {
buf = append(buf, '_')
} else {
buf = strconv.AppendInt(buf, int64(edgeLen[i][j]), 10)
}
}
}
return string(buf)
}
func isRealizable(n int) bool {
adj := make([][]int, n)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if edgeLen[i][j] != -1 {
adj[i] = append(adj[i], j)
adj[j] = append(adj[j], i)
}
}
}
disc := make([]int, n)
low := make([]int, n)
timer := 0
type Edge struct{ u, v int }
stack := make([]Edge, 0)
blocks := make([][]int, 0)
var dfs func(int, int)
dfs = func(u, parent int) {
timer++
disc[u] = timer
low[u] = timer
for _, v := range adj[u] {
if disc[v] == 0 {
stack = append(stack, Edge{u, v})
dfs(v, u)
if low[v] < low[u] {
low[u] = low[v]
}
if low[v] >= disc[u] {
used := make([]bool, n)
comp := make([]int, 0)
for len(stack) > 0 {
e := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if !used[e.u] {
used[e.u] = true
comp = append(comp, e.u)
}
if !used[e.v] {
used[e.v] = true
comp = append(comp, e.v)
}
if (e.u == u && e.v == v) || (e.u == v && e.v == u) {
break
}
}
blocks = append(blocks, comp)
}
} else if v != parent && disc[v] < disc[u] {
stack = append(stack, Edge{u, v})
if disc[v] < low[u] {
low[u] = disc[v]
}
}
}
}
for i := 0; i < n; i++ {
if disc[i] == 0 {
dfs(i, -1)
if len(stack) > 0 {
used := make([]bool, n)
comp := make([]int, 0)
for len(stack) > 0 {
e := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if !used[e.u] {
used[e.u] = true
comp = append(comp, e.u)
}
if !used[e.v] {
used[e.v] = true
comp = append(comp, e.v)
}
}
blocks = append(blocks, comp)
}
}
}
for _, b := range blocks {
if !solveBlock(b) {
return false
}
}
return true
}
func solveBlock(verts []int) bool {
m := len(verts)
if m <= 2 {
return true
}
local := make([][]int, m)
for i := 0; i < m; i++ {
local[i] = make([]int, m)
for j := 0; j < m; j++ {
local[i][j] = -1
}
}
for i := 0; i < m; i++ {
for j := i + 1; j < m; j++ {
local[i][j] = edgeLen[verts[i]][verts[j]]
local[j][i] = local[i][j]
}
}
type Triple struct{ a, b, c int }
triples := make([]Triple, 0)
for i := 0; i < m; i++ {
for j := i + 1; j < m; j++ {
if local[i][j] == -1 {
continue
}
for k := j + 1; k < m; k++ {
if local[i][k] != -1 && local[j][k] != -1 {
triples = append(triples, Triple{i, j, k})
}
}
}
}
if len(triples) == 0 {
return false
}
for _, tr := range triples {
ab2 := float64(local[tr.a][tr.b])
ac2 := float64(local[tr.a][tr.c])
bc2 := float64(local[tr.b][tr.c])
ab := math.Sqrt(ab2)
x := (ac2 - bc2 + ab2) / (2 * ab)
y2 := ac2 - x*x
if y2 <= 1e-9 {
continue
}
y := math.Sqrt(y2)
coords := make([]Point, m)
placed := make([]bool, m)
coords[tr.a] = Point{0, 0}
coords[tr.b] = Point{ab, 0}
coords[tr.c] = Point{x, y}
placed[tr.a] = true
placed[tr.b] = true
placed[tr.c] = true
if placeRest(local, coords, placed, 3) {
return true
}
}
return false
}
func placeRest(edge [][]int, coords []Point, placed []bool, cnt int) bool {
m := len(edge)
if cnt == m {
return true
}
sel := -1
bestCnt := -1
for v := 0; v < m; v++ {
if placed[v] {
continue
}
c := 0
for u := 0; u < m; u++ {
if placed[u] && edge[v][u] != -1 {
c++
}
}
if c > bestCnt {
bestCnt = c
sel = v
}
}
if sel == -1 {
return true
}
if bestCnt < 2 {
return false
}
neigh := make([]int, 0)
for u := 0; u < m; u++ {
if placed[u] && edge[sel][u] != -1 {
neigh = append(neigh, u)
}
}
u0, u1 := -1, -1
bestD := -1.0
for i := 0; i < len(neigh); i++ {
for j := i + 1; j < len(neigh); j++ {
d := dist2(coords[neigh[i]], coords[neigh[j]])
if d > bestD {
bestD = d
u0 = neigh[i]
u1 = neigh[j]
}
}
}
if u0 == -1 {
return false
}
cands := circleIntersections(coords[u0], coords[u1], float64(edge[sel][u0]), float64(edge[sel][u1]))
for _, p := range cands {
ok := true
for u := 0; u < m; u++ {
if !placed[u] {
continue
}
d2 := dist2(p, coords[u])
if d2 < 1e-8 {
ok = false
break
}
if edge[sel][u] != -1 && math.Abs(d2-float64(edge[sel][u])) > 1e-5 {
ok = false
break
}
}
if ok {
coords[sel] = p
placed[sel] = true
if placeRest(edge, coords, placed, cnt+1) {
return true
}
placed[sel] = false
}
}
return false
}
func circleIntersections(a, b Point, ra2, rb2 float64) []Point {
dx := b.x - a.x
dy := b.y - a.y
d2 := dx*dx + dy*dy
if d2 < 1e-12 {
return nil
}
d := math.Sqrt(d2)
sum := math.Sqrt(ra2) + math.Sqrt(rb2)
diff := math.Abs(math.Sqrt(ra2) - math.Sqrt(rb2))
if d > sum+1e-8 || d < diff-1e-8 {
return nil
}
x := (ra2 - rb2 + d2) / (2 * d)
h2 := ra2 - x*x
if h2 < -1e-8 {
return nil
}
if h2 < 0 {
h2 = 0
}
mx := a.x + x*dx/d
my := a.y + x*dy/d
if h2 <= 1e-9 {
return []Point{{mx, my}}
}
h := math.Sqrt(h2)
rx := -dy * h / d
ry := dx * h / d
p1 := Point{mx + rx, my + ry}
p2 := Point{mx - rx, my - ry}
if dist2(p1, p2) < 1e-10 {
return []Point{p1}
}
return []Point{p1, p2}
}
func dist2(a, b Point) float64 {
dx := a.x - b.x
dy := a.y - b.y
return dx*dx + dy*dy
}