How to calculate number of rectangles in rectangular grid?

I want to calculate number of rectangles in a rectangles.It can be done using formula

(x^2+x)(y^2+y)/4

but it also includes perfect squares like 1*1,2*2,3*3 etc.I dont want to include that in my calculations.How can 开发者_运维技巧i do that?

Ok, you have the number of rectangles with integer coordinates between the points (0, 0), (x, 0), (x, y) and (0, y), x and y being integers too. You now need to remove the perfect squares from this sum.

To compute it, let's evaluate the number of squares 1*1: there are obviously x*y of them. For squares 2*2, we have x-1 choices for the x-coordinate and y-1 for the y-coordinate of the bottom left-hand corner of such a square, due to the width of this square: this results in (x-1)*(y-1) squares. Idem, we will have (x-2)*(y-2) squares 3*3, etc.

So for a given i, we have (x - i + 1) * (y - i + 1) squares i*i, and i goes from 1 to the minimum of x and y (of course if x is 4 and y is 7, we cannot have a square with a side greater than 4).

So if m = min(x, y), we have:

Sum_Squares = Sum(i = 1, i = m, (x - i + 1) * (y - i + 1))
            = Sum(j = 0, j = m - 1, (x - i) * (y - i))
            = Sum(j = 0, j = m - 1, x*y - (x+y)*j + j^2)
            = m*x*y - (x+y)*Sum(j = 0, j = m - 1, j) + Sum(j = 0, j = m - 1, j^2)
            = m*x*y - (x+y)*Sum(j = 1, j = m - 1, j) + Sum(j = 1, j = m - 1, j^2)
            = m*x*y - (x+y)*m*(m-1)/2 + (m-1)*m*(2*m-1)/6

I get that with an index change (j = i - 1) and via the well-known formulas:

Sum(i = 1, i = n, j) = n*(n + 1)/2
Sum(i = 1, i = n, j^2) = n*(n + 1)*(2*n + 1)/6

You just have to remove this Sum_Squares from (x^2+x)(y^2+y)/4 and you're done !