← Home
package main

import (
	"fmt"
	"sort"
)

type Point struct {
	x, y int
}

func crossProduct(o, a, b Point) int {
	return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x)
}

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

	var hull []Point
	for _, p := range points {
		for len(hull) >= 2 && crossProduct(hull[len(hull)-2], hull[len(hull)-1], p) <= 0 {
			hull = hull[:len(hull)-1]
		}
		hull = append(hull, p)
	}

	t := len(hull)
	for i := len(points) - 2; i >= 0; i-- {
		p := points[i]
		for len(hull) > t && crossProduct(hull[len(hull)-2], hull[len(hull)-1], p) <= 0 {
			hull = hull[:len(hull)-1]
		}
		hull = append(hull, p)
	}

	if len(hull) > 1 {
		hull = hull[:len(hull)-1]
	}
	return hull
}

func main() {
	var n, r int
	if _, err := fmt.Scan(&n, &r); err != nil {
		return
	}

	var points []Point
	for x := -r; x <= r; x++ {
		for y := -r; y <= r; y++ {
			if x*x+y*y <= r*r {
				points = append(points, Point{x, y})
			}
		}
	}

	hull := convexHull(points)

	var dp [9][481][481]int
	var parent [9][481][481]Point

	for i := 0; i <= n; i++ {
		for j := 0; j <= 480; j++ {
			for k := 0; k <= 480; k++ {
				dp[i][j][k] = -1
			}
		}
	}

	dp[0][240][240] = 0

	for i := 0; i < n; i++ {
		for sx := 0; sx <= 480; sx++ {
			for sy := 0; sy <= 480; sy++ {
				if dp[i][sx][sy] != -1 {
					for _, p := range hull {
						nsx := sx + p.x
						nsy := sy + p.y
						nval := dp[i][sx][sy] + p.x*p.x + p.y*p.y
						if nval > dp[i+1][nsx][nsy] {
							dp[i+1][nsx][nsy] = nval
							parent[i+1][nsx][nsy] = p
						}
					}
				}
			}
		}
	}

	maxSum := -1
	bestSx, bestSy := -1, -1

	for sx := 0; sx <= 480; sx++ {
		for sy := 0; sy <= 480; sy++ {
			if dp[n][sx][sy] != -1 {
				realSx := sx - 240
				realSy := sy - 240
				val := n*dp[n][sx][sy] - realSx*realSx - realSy*realSy
				if val > maxSum {
					maxSum = val
					bestSx = sx
					bestSy = sy
				}
			}
		}
	}

	fmt.Println(maxSum)
	currSx, currSy := bestSx, bestSy
	for i := n; i > 0; i-- {
		p := parent[i][currSx][currSy]
		fmt.Printf("%d %d\n", p.x, p.y)
		currSx -= p.x
		currSy -= p.y
	}
}