*R*rectangle

*a x b*of integer size. Each rectangle contains unit blocks, consider the diagonal and count how many blocks

*c*are touched by the diagonal. Given a value K how many rectangles have exactly K block touching the diagonal? here an example

I found this problem online but was not able to solve it so far

Since I've a CG background, my answer is: use Bresenham's algorithm

ReplyDeletegcd(a, b) + a + b - 1

ReplyDeletex = gcd(a, b)

ReplyDeleteanswer = x + a/x + b/x - 1

thanks Stefano, that was good.

ReplyDelete