# ruby implementation of the Graham Scan Algorithm
# finds the convex hull of a set of unordered points
# (c) Yoann Guillot, 09/2008, WTFPL

# takes a list of couples of floats, eg [[1.4, 2.7], [1.4, 3.8]]
def grahamscan(list)
	isleft = proc { |p1, p2, p3|
		((p2[0]-p1[0]) * (p3[1]-p1[1])) - ((p3[0]-p1[0]) * (p2[1]-p1[1])) >= 0
	}

	pivot = list.sort.first	# lower x, then lower y
	sorted = [pivot] + (list - [pivot]).sort_by { |x, y|
		dx, dy = x-pivot[0], y-pivot[1]
		[dy/dx, dx.abs, dy.abs]
       	}
	stack = [sorted.shift, sorted.shift]
	sorted.each { |p|
		stack.pop while stack.length > 2 and isleft[stack[-2], p, stack[-1]]
		stack << p
	}
	stack
end

if $0 == __FILE__
	# generate this much points
	num = (ARGV.shift || 40).to_i

	# console size
	MAXX = (ARGV.shift || 78).to_i/2
	MAXY = (ARGV.shift || 25).to_i

	list = Array.new(num) { [rand(MAXX).to_f, rand(MAXY).to_f] }.uniq

	# framebuffer
	buf = Array.new(MAXY) { ' '*MAXX }
	list.each { |x, y| buf[y][x] = '.' }
	grahamscan(list).each { |x, y| buf[y][x] = 'x' }

	# render
	puts buf.reverse.map { |l| l.split(//).join(' ') }
end