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