PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
To detect whether the quadrangle has an integer area we will use the Pick theorem which states that the area of a grid polygon can be calculated in the following way S = W + I/2 - 1. Where W is the amount of lattice points strictly inside the polygon and I is the amount of lattice points on its edge. So the area S will be integer if the amount of lattice points on its edge will be even. Now how we will count the amount of lattice points on the edge of a given quadrangle.
Let us consider any quadrangle ABCD the edges of which don’t intersect. Let’s look at its edge AB. The amount of lattice points lying on that edge can be calculated as gcd(|Ax – Bx|, |Ay – By|) + 1, where gcd is the greatest common divisor. Or it will be gcd(|Ax - Bx|, |Ay - By|) – 1 if we don’t count the points on the ends of segment AB.
So now if we count the same value for each edge we will have the following expression for I = gcd(|Ax - Bx|, |Ay - By|) + gcd(|Bx - Cx|, |By - Cy|) + gcd(|Cx - Dx|, |Cy - Dy|) + gcd(|Dx - Ax|, |Dy - Ay|) (1). But we only need to each if that value is odd or even. For two given non-negative integers gcd(a, b) is even iff a and b are both even. So gcd(|Ax - Bx|, |Ay - By|) is even iff |Ax – Bx| and |Ay – By| are both even. Now |Ax – Bx| is even iff Ax and Bx are both even of both odd. So gcd(|Ax - Bx|, |Ay - By|) is even when the Ax and Bx have the same remainder modulo 2 and Ay and By have the same remainder modulo 2. That means that we don’t need to know the exact value of Ax, Ay, Bx, By, but only their remainders modulo 2. That is true for all other points as well. After we find if any of the gcds in (1) are odd or even we can easily determine if I is odd or even.
Next is how to count all the quadrangles with the stated quality. First we need to split the given point into four groups: the first group with x > 0 and y > 0, the second – x > 0 and y < 0, the third x < 0 and y < 0 and the fourth – x < 0 and y > 0. Then in each group we need to split all points of the group into four groups again: the first group with x even and y even, the second – x even and y odd, the third – x odd and y even and the fourth – x odd and y odd. We will count the amount of points in each group and each subgroup as well. After that we can iterate over all possible variants of taking points from the group. Surely to form a triangle we have to take one point from each group of the first type. Then we try all possible assignment of points from the subgroups.
There are in total 4^4 different types of quadrangles we can form. For each type we know the amount of quadrangles of that type and we can determine if the area of quadrangles of such type is an integer. So we try all those types and if the area is an integer we add the amount of those quadrangles to the answer.
The complexity of the described algorithm is O(n).