Computation Workshop Solution Checker

Diagonal Polygons

Let \(N\) be a fixed positive integer. A lattice point is any point \((x,y)\) in the Cartesean plane such that both \(x\) and \(y\) are integers with \(0 \leq x < N\) and \(0 \leq y < N\). A polygon is called a `Diagonal Polygon' if all of its vertices are lattice points and all its side-lengths are exactly \(\sqrt{2}\). Let \(D\) denote the total number of diagonal polygons. For example when \(N=5\), we have \(D=10\) (nine of them are squares and the last one is a Greek cross shape).

[Note that the boundary of a polygon is not allowed to self-intersect]