← Home
For problem statement at 0-999/100-199/140-149/140/problemF.txt this is a correct solution, but verifier at 0-999/100-199/140-149/140/verifierF.go ends with case 1 failed: expected 3
8.0 3.0
8.0 5.5
9.0 5.5 got 3
8.0000000000 3.0000000000
8.0000000000 5.5000000000
9.0000000000 5.5000000000
input:
3 1
9 3
9 8
7 3
exit status 1 can you fix the verifier? package main

import (
	"bytes"
	"fmt"
	"io"
	"os"
	"sort"
)

type FastScanner struct {
	data []byte
	idx  int
}

func (fs *FastScanner) NextInt64() int64 {
	n := len(fs.data)
	for fs.idx < n && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
	sign := int64(1)
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	var v int64
	for fs.idx < n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		v = v*10 + int64(c-'0')
		fs.idx++
	}
	return sign * v
}

type Pt struct {
	x, y int64
}

type Node struct {
	key int64
	p   Pt
}

const (
	base int64 = 1000000001
	off  int64 = 2000000000
)

func enc(x, y int64) uint64 {
	return uint64(uint32(x+off))<<32 | uint64(uint32(y+off))
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	fs := FastScanner{data: data}

	n := int(fs.NextInt64())
	k := int(fs.NextInt64())

	if n <= k {
		fmt.Print("-1")
		return
	}

	nodes := make([]Node, n)
	set := make(map[uint64]struct{}, n*2)

	for i := 0; i < n; i++ {
		x := fs.NextInt64()
		y := fs.NextInt64()
		p := Pt{x, y}
		nodes[i] = Node{key: x*base + y, p: p}
		set[enc(x, y)] = struct{}{}
	}

	sort.Slice(nodes, func(i, j int) bool {
		return nodes[i].key < nodes[j].key
	})

	pts := make([]Pt, n)
	for i := 0; i < n; i++ {
		pts[i] = nodes[i].p
	}

	t := k + 1
	if t > n {
		t = n
	}

	cand := make(map[Pt]struct{}, t*t)
	for i := 0; i < t; i++ {
		for j := n - t; j < n; j++ {
			s := Pt{pts[i].x + pts[j].x, pts[i].y + pts[j].y}
			cand[s] = struct{}{}
		}
	}

	ans := make([]Pt, 0, len(cand))
	for s := range cand {
		miss := 0
		for _, p := range pts {
			if _, ok := set[enc(s.x-p.x, s.y-p.y)]; !ok {
				miss++
				if miss > k {
					break
				}
			}
		}
		if miss <= k {
			ans = append(ans, s)
		}
	}

	sort.Slice(ans, func(i, j int) bool {
		if ans[i].x != ans[j].x {
			return ans[i].x < ans[j].x
		}
		return ans[i].y < ans[j].y
	})

	var out bytes.Buffer
	fmt.Fprintf(&out, "%d\n", len(ans))
	for _, s := range ans {
		fmt.Fprintf(&out, "%.10f %.10f\n", float64(s.x)/2.0, float64(s.y)/2.0)
	}
	os.Stdout.Write(out.Bytes())
}