For problem statement at 0-999/600-699/690-699/690/problemB2.txt this is a correct solution, but verifier at 0-999/600-699/690-699/690/verifierB2.go ends with All 60 tests passed can you fix the verifier? package main
import (
"bufio"
"io"
"os"
)
type Point struct {
x int
y int
}
func nextInt(data []byte, idx *int) int {
n := len(data)
for *idx < n && data[*idx] <= ' ' {
*idx++
}
sign := 1
if *idx < n && data[*idx] == '-' {
sign = -1
*idx++
}
val := 0
for *idx < n && data[*idx] > ' ' {
val = val*10 + int(data[*idx]-'0')
*idx++
}
return sign * val
}
func nextToken(data []byte, idx *int) []byte {
n := len(data)
for *idx < n && data[*idx] <= ' ' {
*idx++
}
start := *idx
for *idx < n && data[*idx] > ' ' {
*idx++
}
return data[start:*idx]
}
func cross(o, a, b Point) int64 {
return int64(a.x-o.x)*int64(b.y-o.y) - int64(a.y-o.y)*int64(b.x-o.x)
}
func convexHullSorted(pts []Point) []Point {
if len(pts) <= 1 {
return pts
}
lower := make([]Point, 0, len(pts))
for _, p := range pts {
for len(lower) >= 2 && cross(lower[len(lower)-2], lower[len(lower)-1], p) <= 0 {
lower = lower[:len(lower)-1]
}
lower = append(lower, p)
}
upper := make([]Point, 0, len(pts))
for i := len(pts) - 1; i >= 0; i-- {
p := pts[i]
for len(upper) >= 2 && cross(upper[len(upper)-2], upper[len(upper)-1], p) <= 0 {
upper = upper[:len(upper)-1]
}
upper = append(upper, p)
}
hull := make([]Point, 0, len(lower)+len(upper)-2)
hull = append(hull, lower[:len(lower)-1]...)
hull = append(hull, upper[:len(upper)-1]...)
return hull
}
func writeInt(w *bufio.Writer, x int) {
if x == 0 {
w.WriteByte('0')
return
}
if x < 0 {
w.WriteByte('-')
x = -x
}
var buf [20]byte
i := len(buf)
for x > 0 {
i--
buf[i] = byte('0' + x%10)
x /= 10
}
w.Write(buf[i:])
}
func main() {
data, _ := io.ReadAll(os.Stdin)
idx := 0
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
for {
n := nextInt(data, &idx)
if n == 0 {
break
}
c := make([][]int, n+1)
a := make([][]int, n+1)
for i := 0; i <= n; i++ {
c[i] = make([]int, n+1)
a[i] = make([]int, n+1)
}
for y := n; y >= 1; y-- {
row := nextToken(data, &idx)
for x := 1; x <= n; x++ {
c[x][y] = int(row[x-1] - '0')
}
}
cnt := 0
for y := 1; y <= n; y++ {
for x := 1; x <= n; x++ {
v := c[x][y] - a[x-1][y-1] - a[x][y-1] - a[x-1][y]
a[x][y] = v
if v == 1 {
cnt++
}
}
}
pts := make([]Point, 0, cnt)
for x := 1; x <= n; x++ {
for y := 1; y <= n; y++ {
if a[x][y] == 1 {
pts = append(pts, Point{x, y})
}
}
}
hull := convexHullSorted(pts)
writeInt(out, len(hull))
out.WriteByte('\n')
writeInt(out, hull[0].x)
out.WriteByte(' ')
writeInt(out, hull[0].y)
out.WriteByte('\n')
for i := len(hull) - 1; i >= 1; i-- {
writeInt(out, hull[i].x)
out.WriteByte(' ')
writeInt(out, hull[i].y)
out.WriteByte('\n')
}
}
}