http://codeforces.com/gym/101164/problem/A

a.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"unicode"
)

var stdReader *bufio.Reader = bufio.NewReader(os.Stdin)

func readInt() (result int) {
	var negative, started bool
READER_LOOP:
	for {
		char, err := stdReader.ReadByte()
		switch {
		case err != nil:
			break READER_LOOP
		case char == '-':
			negative = true
		case unicode.IsDigit(rune(char)):
			started = true
			result = result*10 + int(char&0xf)
		case started:
			break READER_LOOP
		}
	}
	if negative {
		result = -result
	}
	return
}

type point struct {
	x, y int
}

// rect stores lowest and highest points of a rectangle.
type rect struct {
	lo, hi point
}

// longestEdge returns longest edge of the rectangle.
func longestEdge(r rect) int {
	x, y := r.hi.x-r.lo.x, r.hi.y-r.lo.y
	if x > y {
		return x
	}
	return y
}

// inside checks if point p is inside rectangle bonud by lo and hi.
func inside(p point, r rect) bool {
	return p.x >= r.lo.x && p.y >= r.lo.y && p.x <= r.hi.x && p.y <= r.hi.y
}

// bounds calculates the smallest rectangular containing all the points.
func bounds(points []point) rect {
	first := true
	var b rect
	for _, p := range points {
		if first || p.x < b.lo.x {
			b.lo.x = p.x
		}
		if first || p.y < b.lo.y {
			b.lo.y = p.y
		}
		if first || p.x > b.hi.x {
			b.hi.x = p.x
		}
		if first || p.y > b.hi.y {
			b.hi.y = p.y
		}
		first = false
	}
	return b
}

// pick builds a rectangular in on of the corners of rectangle bound by lo and hi.
func pick(side, edge int, b rect) rect {
	switch side {
	case 0:
		return rect{b.lo, point{b.lo.x + edge, b.lo.y + edge}}
	case 1:
		return rect{point{b.hi.x - edge, b.lo.y}, point{b.hi.x, b.lo.y + edge}}
	case 2:
		return rect{point{b.hi.x - edge, b.hi.y - edge}, b.hi}
	case 3:
		return rect{point{b.lo.x, b.hi.y - edge}, point{b.lo.x + edge, b.hi.y}}
	default:
		panic("Unexpected side")
	}
}

// feasible checks if we can cover poits by three rectangles with specified edge.
func feasible(edge int, points []point) bool {
	b := bounds(points)
	for i := 0; i < 4; i++ {
		corner := pick(i, edge, b)
		var loose []point
		for _, p := range points {
			if !inside(p, corner) {
				loose = append(loose, p)
			}
		}

		looseBounds := bounds(loose)
		midx, midy := looseBounds.lo.x+edge, looseBounds.lo.y+edge
		var left, right, top, bottom []point
		for _, p := range loose {
			if p.x <= midx {
				left = append(left, p)
			} else {
				right = append(right, p)
			}
			if p.y <= midy {
				top = append(top, p)
			} else {
				bottom = append(bottom, p)
			}
		}
		leftBounds := bounds(left)
		rightBounds := bounds(right)
		if longestEdge(leftBounds) <= edge && longestEdge(rightBounds) <= edge {
			return true
		}
		topBounds := bounds(top)
		bottomBounds := bounds(bottom)
		if longestEdge(topBounds) <= edge && longestEdge(bottomBounds) <= edge {
			return true
		}
	}
	return false
}

func main() {
	// Reading.
	n := readInt()
	points := make([]point, n)
	for i := range points {
		points[i] = point{readInt(), readInt()}
	}

	// Max possible answer.
	m := longestEdge(bounds(points))

	// Binary search [0, m) so I shift it to [1, m].
	fmt.Println(sort.Search(m, func(edge int) bool {
		return feasible(edge+1, points)
	}) + 1)
}

a_test.go

package main

import "testing"

func TestInside(t *testing.T) {
	var tests = []struct {
		p    point
		r    rect
		want bool
	}{
		{point{0, 0}, rect{point{1, 1}, point{3, 3}}, false},
		{point{2, 0}, rect{point{1, 1}, point{3, 3}}, false},
		{point{0, 2}, rect{point{1, 1}, point{3, 3}}, false},
		{point{4, 0}, rect{point{1, 1}, point{3, 3}}, false},
		{point{0, 4}, rect{point{1, 1}, point{3, 3}}, false},
		{point{1, 3}, rect{point{1, 1}, point{3, 3}}, true},
		{point{3, 2}, rect{point{1, 1}, point{3, 3}}, true},
		{point{2, 2}, rect{point{1, 1}, point{3, 3}}, true},
	}
	for _, test := range tests {
		if got := inside(test.p, test.r); got != test.want {
			t.Errorf("inside(%v, %v) = %t; want %t", test.p, test.r, got, test.want)
		}
	}
}

func TestBounds(t *testing.T) {
	var tests = []struct {
		points []point
		want   rect
	}{
		{
			[]point{{1, 1}, {3, 3}},
			rect{point{1, 1}, point{3, 3}},
		},
		{
			[]point{{3, 1}, {1, 3}},
			rect{point{1, 1}, point{3, 3}},
		},
		{
			[]point{{1, 1}, {3, 3}, {1, 3}, {3, 1}},
			rect{point{1, 1}, point{3, 3}},
		},
		{
			[]point{{0, 0}},
			rect{point{0, 0}, point{0, 0}},
		},
		{
			nil,
			rect{point{0, 0}, point{0, 0}},
		},
		{
			[]point{{1, 2}, {2, 1}, {3, 2}, {4, 1}, {5, 2}, {6, 1}},
			rect{point{1, 1}, point{6, 2}},
		},
		{
			[]point{{2, 1}, {1, 2}, {2, 3}, {1, 4}, {2, 5}, {1, 6}},
			rect{point{1, 1}, point{2, 6}},
		},
	}
	for _, test := range tests {
		if got := bounds(test.points); got != test.want {
			t.Errorf("bounds(%v) = %v; want %v, %v", test.points, got, test.want)
		}
	}
}

func TestPick(t *testing.T) {
	var tests = []struct {
		side, edge  int
		bound, want rect
	}{
		{
			0, 1,
			rect{point{1, 1}, point{3, 3}},
			rect{point{1, 1}, point{2, 2}},
		},
		{
			1, 1,
			rect{point{1, 1}, point{3, 3}},
			rect{point{2, 1}, point{3, 2}},
		},
		{
			2, 1,
			rect{point{1, 1}, point{3, 3}},
			rect{point{2, 2}, point{3, 3}},
		},
		{
			3, 1,
			rect{point{1, 1}, point{3, 3}},
			rect{point{1, 2}, point{2, 3}},
		},
	}
	for _, test := range tests {
		if got := pick(test.side, test.edge, test.bound); got != test.want {
			t.Errorf("pick(%d, %d, %v) = %v; want %v", test.side, test.edge, test.bound, got, test.want)
		}
	}
}