# Counting simple quadrilaterals in a rectangular lattice.

I've been trying to make an algorithm to find the number of all possible simple quadrilaterals in a N*M lattice. I already have a brute force solution but since this is a Project Euler problem I believe it should be possible to solve much faster than I'm doing and so I'm taking a math approach instead. I haven't figured out much unfortunately. I tried to go about this using binomial coefficients and failed. Now I'm trying to use Pick's theorem which pretty much ensures we are dealing with simple polygons but I am not sure how to handle overlapping quads. The reason I'm posting therefore is to see if there is any other math approach I can take. I don't want any solutions just clues on the math part since I am not that educated on these math subjects.

Edit: I took a completely different approach so this has no need for me anymore. I am leaving it open for others.

• How do you count lattice quadrilaterals with three collinear vertices? – Christian Blatter Feb 4 '14 at 19:45
• In the old code using slopes. The very inefficient part of my previous code was checking which points can form 1 or 3 quads. I am sure there is a very elegant solution I'm not seeing. – Veritas Feb 4 '14 at 19:53
• I have a O(m^2 n^2 k) algorithm for it, but I think it can be solved faster – Xeing Mar 26 '14 at 9:28