Thought Process

This was quite an easy problem.

Any sort of research should lead you to Pick's Theorem from there the problem is basically solved.

Pick's Theorem states: A = i + b/2 - 1, where A = Area of Quadrilateral, i = Number of interior lattice points, b = Number of lattice boundary points

Calculating the area is simple, split it up into 4 triangles and we have that the area is (a + c)(b + d)/2

Now we just need to calculate the number of boundary points. Playing around with desmos I noticed that the segment between A and B always has gcd(a, b) - 1 boundary lattice points (Excluding the points A and B), if it is true then our problem is solved so we just need to prove it.

Suppose g = gcd(a, b) the segment between A and B can be parameterized by y = (-b/a)x + b, 0 ≤ x ≤ a (I leave it to you to figure out how to get this)

We want integer points on this line, that is, the integer x values such that (-b/a)x is an integer. We simplify (-b/a) using its gcd.

If a = gk, b = gl, then we have that (-b/a)x = (-l/k)x, therefore, in order for this to be an integer x must be a multiple of k, and 0 ≤ x ≤ a = gk there will be exactly g - 1 of them.

Now we conclude that for given a,b,c,d the number of interior points is, ((a + c)(b + d) -(gcd(a,b) + gcd(b,c) + gcd(a,d) + gcd(c,d))/2 +1. We did this using i = A - b/2 + 1.

Note that we added the 4 points A, B, C, D themselves.

From here I just looped through all possible a,b,c,d with a pre-computed gcd table and got the answer in around ~100s but it could definetly be made faster