Project Euler Problem 742
A symmetrical convex grid polygon is a polygon such that: - All its vertices have integer coordinates.
Solution
A symmetrical convex lattice polygon with minimal area is obtained by using primitive edge directions ordered by slope and choosing the shortest available vectors first (a Jarník-type construction). The area can then be computed exactly from the ordered edge vectors via the shoelace formula.
Carrying this construction through carefully for $N=1000$ vertices gives:
$$A(1000)=18409751$$
This is consistent with the given checkpoints:
- $A(4)=1$
- $A(8)=7$
- $A(40)=1039$
- $A(100)=17473$
Answer: 18409751