For problem statement at 0-999/200-299/270-279/274/problemC.txt this is a correct solution, but verifier at 0-999/200-299/270-279/274/verifierC.go ends with All tests passed can you fix the verifier? package main
import (
"bufio"
"fmt"
"math"
"math/bits"
"os"
"sort"
)
const maxWords = 76
type Point struct {
x, y int64
}
type Rat struct {
hi, lo, den uint64
}
type Edge struct {
u, v int
val Rat
cycle int
}
type Triangle struct {
ids [3]int32
val Rat
}
type DSU struct {
p []int
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 {
for d.p[x] != x {
d.p[x] = d.p[d.p[x]]
x = d.p[x]
}
return x
}
func (d *DSU) Union(a, b int) bool {
ra := d.Find(a)
rb := d.Find(b)
if ra == rb {
return false
}
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]++
}
return true
}
func dist2(a, b Point) uint64 {
dx := a.x - b.x
dy := a.y - b.y
return uint64(dx*dx + dy*dy)
}
func mul128by64(hi, lo, x uint64) (w2, w1, w0 uint64) {
p1hi, p1lo := bits.Mul64(lo, x)
p2hi, p2lo := bits.Mul64(hi, x)
w0 = p1lo
w1, xcarry := bits.Add64(p1hi, p2lo, 0)
w2 = p2hi + xcarry
return
}
func cmpRat(a, b Rat) int {
if a.den == b.den {
if a.hi < b.hi {
return -1
}
if a.hi > b.hi {
return 1
}
if a.lo < b.lo {
return -1
}
if a.lo > b.lo {
return 1
}
return 0
}
a2, a1, a0 := mul128by64(a.hi, a.lo, b.den)
b2, b1, b0 := mul128by64(b.hi, b.lo, a.den)
if a2 < b2 {
return -1
}
if a2 > b2 {
return 1
}
if a1 < b1 {
return -1
}
if a1 > b1 {
return 1
}
if a0 < b0 {
return -1
}
if a0 > b0 {
return 1
}
return 0
}
func triangleRat(i, j, k int, pts []Point, d2 [][]uint64) Rat {
a2 := d2[j][k]
b2 := d2[i][k]
c2 := d2[i][j]
l2 := a2
if b2 > l2 {
l2 = b2
}
if c2 > l2 {
l2 = c2
}
if l2 >= a2+b2+c2-l2 {
return Rat{0, l2, 4}
}
cross := (pts[j].x-pts[i].x)*(pts[k].y-pts[i].y) - (pts[j].y-pts[i].y)*(pts[k].x-pts[i].x)
if cross < 0 {
cross = -cross
}
den := 4 * uint64(cross) * uint64(cross)
hi1, lo1 := bits.Mul64(a2, b2)
w2, w1, w0 := mul128by64(hi1, lo1, c2)
_ = w2
return Rat{w1, w0, den}
}
func highBitWords(col *[maxWords]uint64, words int) int {
for i := words - 1; i >= 0; i-- {
if x := col[i]; x != 0 {
return i*64 + bits.Len64(x) - 1
}
}
return -1
}
func ratFloat(r Rat) float64 {
return (math.Ldexp(float64(r.hi), 64) + float64(r.lo)) / float64(r.den)
}
func main() {
in := bufio.NewReaderSize(os.Stdin, 1<<20)
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
var n int
fmt.Fscan(in, &n)
pts := make([]Point, n)
for i := 0; i < n; i++ {
fmt.Fscan(in, &pts[i].x, &pts[i].y)
}
if n < 3 {
fmt.Fprintln(out, -1)
return
}
d2 := make([][]uint64, n)
for i := range d2 {
d2[i] = make([]uint64, n)
}
edges := make([]Edge, 0, n*(n-1)/2)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
d := dist2(pts[i], pts[j])
d2[i][j] = d
d2[j][i] = d
edges = append(edges, Edge{u: i, v: j, val: Rat{0, d, 4}, cycle: -1})
}
}
sort.Slice(edges, func(i, j int) bool {
c := cmpRat(edges[i].val, edges[j].val)
if c != 0 {
return c < 0
}
if edges[i].u != edges[j].u {
return edges[i].u < edges[j].u
}
return edges[i].v < edges[j].v
})
cycleMat := make([][]int, n)
for i := 0; i < n; i++ {
cycleMat[i] = make([]int, n)
for j := 0; j < n; j++ {
cycleMat[i][j] = -1
}
}
ds := NewDSU(n)
cycleCount := 0
for i := range edges {
if ds.Union(edges[i].u, edges[i].v) {
edges[i].cycle = -1
} else {
edges[i].cycle = cycleCount
cycleMat[edges[i].u][edges[i].v] = cycleCount
cycleMat[edges[i].v][edges[i].u] = cycleCount
cycleCount++
}
}
tris := make([]Triangle, 0, n*(n-1)*(n-2)/6)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
t := Triangle{val: triangleRat(i, j, k, pts, d2)}
t.ids[0] = int32(cycleMat[i][j])
t.ids[1] = int32(cycleMat[i][k])
t.ids[2] = int32(cycleMat[j][k])
tris = append(tris, t)
}
}
}
sort.Slice(tris, func(i, j int) bool {
c := cmpRat(tris[i].val, tris[j].val)
if c != 0 {
return c < 0
}
if tris[i].ids[0] != tris[j].ids[0] {
return tris[i].ids[0] < tris[j].ids[0]
}
if tris[i].ids[1] != tris[j].ids[1] {
return tris[i].ids[1] < tris[j].ids[1]
}
return tris[i].ids[2] < tris[j].ids[2]
})
hasPivot := make([]bool, cycleCount)
pivotData := make([][maxWords]uint64, cycleCount)
epos, tpos := 0, 0
cycleAdded, rank := 0, 0
seenHole := false
hasAns := false
var ans Rat
for epos < len(edges) || tpos < len(tris) {
var cur Rat
if tpos == len(tris) || (epos < len(edges) && cmpRat(edges[epos].val, tris[tpos].val) < 0) {
cur = edges[epos].val
} else {
cur = tris[tpos].val
}
betaBefore := cycleAdded - rank
for epos < len(edges) && cmpRat(edges[epos].val, cur) == 0 {
if edges[epos].cycle >= 0 {
cycleAdded++
}
epos++
}
for tpos < len(tris) && cmpRat(tris[tpos].val, cur) == 0 {
var col [maxWords]uint64
p := -1
for _, v := range tris[tpos].ids {
id := int(v)
if id >= 0 {
col[id>>6] ^= uint64(1) << (uint(id) & 63)
if id > p {
p = id
}
}
}
for p >= 0 {
if !hasPivot[p] {
hasPivot[p] = true
pivotData[p] = col
rank++
break
}
pw := p >> 6
pd := &pivotData[p]
for i := 0; i <= pw; i++ {
col[i] ^= pd[i]
}
p = highBitWords(&col, pw+1)
}
tpos++
}
betaAfter := cycleAdded - rank
if betaAfter > 0 {
seenHole = true
}
if betaBefore > 0 && betaAfter == 0 {
ans = cur
hasAns = true
}
}
if !seenHole || !hasAns {
fmt.Fprintln(out, -1)
return
}
fmt.Fprintf(out, "%.10f\n", math.Sqrt(ratFloat(ans)))
}