For problem statement at 0-999/800-899/880-889/886/problemF.txt this is a correct solution, but verifier at 0-999/800-899/880-889/886/verifierF.go ends with All tests passed can you fix the verifier? package main
import (
"bufio"
"fmt"
"math/bits"
"os"
"sort"
)
type Point struct {
x, y int64
}
type Vec struct {
x, y int64
}
type Int128 struct {
h int64
l uint64
}
func mulSigned(a, b int64) Int128 {
sign := int64(1)
if a < 0 {
sign = -sign
a = -a
}
if b < 0 {
sign = -sign
b = -b
}
h_u, l := bits.Mul64(uint64(a), uint64(b))
h := int64(h_u)
if sign < 0 {
l = ^l + 1
h = ^h
if l == 0 {
h++
}
}
return Int128{h, l}
}
func sub128(a, b Int128) Int128 {
l := a.l - b.l
h := a.h - b.h
if a.l < b.l {
h--
}
return Int128{h, l}
}
func add128(a, b Int128) Int128 {
l := a.l + b.l
h := a.h + b.h
if l < a.l {
h++
}
return Int128{h, l}
}
func isZero(a Int128) bool {
return a.h == 0 && a.l == 0
}
func less(a, b Int128) bool {
if a.h != b.h {
return a.h < b.h
}
return a.l < b.l
}
func eval(p Point, v Vec) Int128 {
return sub128(mulSigned(p.x, v.y), mulSigned(p.y, v.x))
}
func gcd(a, b int64) int64 {
for b != 0 {
a, b = b, a%b
}
return a
}
func abs(a int64) int64 {
if a < 0 {
return -a
}
return a
}
func normalize(x, y int64) (int64, int64) {
if x == 0 && y == 0 {
return 0, 0
}
g := gcd(abs(x), abs(y))
x /= g
y /= g
if x < 0 || (x == 0 && y < 0) {
x = -x
y = -y
}
return x, y
}
type Int128Slice []Int128
func (s Int128Slice) Len() int { return len(s) }
func (s Int128Slice) Less(i, j int) bool { return less(s[i], s[j]) }
func (s Int128Slice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func main() {
reader := bufio.NewReader(os.Stdin)
var n int
fmt.Fscan(reader, &n)
pts := make([]Point, n)
var sumX, sumY int64
for i := 0; i < n; i++ {
fmt.Fscan(reader, &pts[i].x, &pts[i].y)
sumX += pts[i].x
sumY += pts[i].y
}
N := int64(n)
P_shifted := make([]Point, n)
for i := 0; i < n; i++ {
P_shifted[i] = Point{
x: N*pts[i].x - sumX,
y: N*pts[i].y - sumY,
}
}
freq := make(map[Point]int)
for _, p := range P_shifted {
neg := Point{-p.x, -p.y}
if freq[neg] > 0 {
freq[neg]--
} else {
freq[p]++
}
}
var S []Point
for p, count := range freq {
for i := 0; i < count; i++ {
if p.x != 0 || p.y != 0 {
S = append(S, p)
}
}
}
if len(S) == 0 {
fmt.Println("-1")
return
}
A := S[0]
candidates := make(map[Vec]bool)
for _, B := range S {
vx := A.x + B.x
vy := A.y + B.y
vx, vy = normalize(vx, vy)
if vx != 0 || vy != 0 {
candidates[Vec{vx, vy}] = true
}
}
validCount := 0
vals := make([]Int128, len(S))
for v := range candidates {
for i, p := range S {
vals[i] = eval(p, v)
}
sort.Sort(Int128Slice(vals))
ok := true
for i := 0; i < len(vals); i++ {
j := len(vals) - 1 - i
if !isZero(add128(vals[i], vals[j])) {
ok = false
break
}
}
if ok {
validCount++
}
}
fmt.Println(validCount)
}