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 case 4 failed: expected "5.412023651094" got "5.412024"
input:
5
1 5
-4 5
0 -5
5 -5
-4 0
exit status 1 can you fix the verifier? package main
import (
"fmt"
"math"
"sort"
"strconv"
"strings"
)
type Point struct {
x, y int
}
func main() {
var n int
if _, err := fmt.Scan(&n); err != nil {
return
}
p := make([]Point, n)
for i := 0; i < n; i++ {
fmt.Scan(&p[i].x, &p[i].y)
}
if n < 3 {
fmt.Println("-1")
return
}
maxR := -1.0
visited := make(map[string]bool)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
cross := int64(p[j].x-p[i].x)*int64(p[k].y-p[i].y) - int64(p[j].y-p[i].y)*int64(p[k].x-p[i].x)
if cross == 0 {
continue
}
isEmpty := true
onCircleIdx := []int{i, j, k}
for m := 0; m < n; m++ {
if m == i || m == j || m == k {
continue
}
inc := inCircle(p[i], p[j], p[k], p[m])
if inc == 1 {
isEmpty = false
break
} else if inc == 0 {
onCircleIdx = append(onCircleIdx, m)
}
}
if !isEmpty {
continue
}
sort.Ints(onCircleIdx)
var sb strings.Builder
for _, idx := range onCircleIdx {
sb.WriteString(strconv.Itoa(idx))
sb.WriteByte(',')
}
hash := sb.String()
if visited[hash] {
continue
}
visited[hash] = true
L := int64(len(onCircleIdx))
var SX, SY int64
for _, idx := range onCircleIdx {
SX += int64(p[idx].x)
SY += int64(p[idx].y)
}
sort.Slice(onCircleIdx, func(a, b int) bool {
idx1 := onCircleIdx[a]
idx2 := onCircleIdx[b]
X1 := L*int64(p[idx1].x) - SX
Y1 := L*int64(p[idx1].y) - SY
X2 := L*int64(p[idx2].x) - SX
Y2 := L*int64(p[idx2].y) - SY
h1 := 2
if Y1 > 0 || (Y1 == 0 && X1 > 0) {
h1 = 1
}
h2 := 2
if Y2 > 0 || (Y2 == 0 && X2 > 0) {
h2 = 1
}
if h1 != h2 {
return h1 < h2
}
c := X1*Y2 - Y1*X2
return c > 0
})
isValid := true
K := len(onCircleIdx)
for r := 0; r < K; r++ {
p1 := p[onCircleIdx[r]]
p2 := p[onCircleIdx[(r+1)%K]]
p3 := p[onCircleIdx[(r+2)%K]]
dx1 := int64(p1.x - p3.x)
dy1 := int64(p1.y - p3.y)
dx2 := int64(p2.x - p3.x)
dy2 := int64(p2.y - p3.y)
dot := dx1*dx2 + dy1*dy2
if dot <= 0 {
isValid = false
break
}
}
if isValid {
a := math.Hypot(float64(p[j].x-p[i].x), float64(p[j].y-p[i].y))
b := math.Hypot(float64(p[k].x-p[j].x), float64(p[k].y-p[j].y))
c_side := math.Hypot(float64(p[i].x-p[k].x), float64(p[i].y-p[k].y))
crossF := math.Abs(float64(cross))
R := (a * b * c_side) / (2.0 * crossF)
if R > maxR {
maxR = R
}
}
}
}
}
if maxR < 0 {
fmt.Println("-1")
} else {
fmt.Printf("%.6f\n", maxR)
}
}
func inCircle(p1, p2, p3, p4 Point) int {
dx2 := int64(p2.x - p1.x)
dy2 := int64(p2.y - p1.y)
dr2 := int64(p2.x*p2.x+p2.y*p2.y) - int64(p1.x*p1.x+p1.y*p1.y)
dx3 := int64(p3.x - p1.x)
dy3 := int64(p3.y - p1.y)
dr3 := int64(p3.x*p3.x+p3.y*p3.y) - int64(p1.x*p1.x+p1.y*p1.y)
dx4 := int64(p4.x - p1.x)
dy4 := int64(p4.y - p1.y)
dr4 := int64(p4.x*p4.x+p4.y*p4.y) - int64(p1.x*p1.x+p1.y*p1.y)
det := dx2*(dy3*dr4-dr3*dy4) - dy2*(dx3*dr4-dr3*dx4) + dr2*(dx3*dy4-dy3*dx4)
cross := dx2*dy3 - dy2*dx3
if cross < 0 {
det = -det
}
if det < 0 {
return 1
} else if det > 0 {
return -1
}
return 0
}