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