forget_it's blog

Help in this Geometrical (counting) concept..
By forget_it, history, 4 years ago, In English

How to count number of squares posible in a m*n grid.

I know formula to count squares which are parallel to given grid. i.e. m*(m+1)*(2m+1)/6 + (n-m)*m*(m+1)/2;

but how to do it for squares which are not parallel to given grid. How to count them??

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Read your question again, slowly.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Errichto had a video where he solved a generalization of this problem on the spot: part (1) was count all axis-aligned rectangles formed by a given set of points, and part (2) was count all general rectangles (your problem asks for only squares, and the set of points is very regular). Nevertheless maybe you can gather some ideas from it:

https://youtu.be/EuPSibuIKIg?t=109

→ Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

ogo tickets..

→ Reply