Lattice point

$m(P,Q)$ is a lattice point if and only if $x_P \equiv x_Q$ and $y_P \equiv y_Q$ mod 2, that is, if the $x$ -coordinates have equal parity (odd or even) and the $y$ -coordinates have equal parity.

Thus we may partition the set $S$ into four "bins", based on whether the coordinates are even or odd. Label these bins $S_1,\dots,S_4$ , and their size $N_1,\dots,N_4$ . The midpoint of two points taken from different bins is never a lattice point. The midpoints of two points from the same bin is always a lattice point. Therefore $X = \sum_{i=1}^4 \text{number of pairs in}\ S_i = \sum_{i=1}^4 \binom{N_i}2 = \sum_{i=1}^4 \tfrac12N_i(N_i-1).$ This sum is minimal if the $N_i$ are chosen to be as similar as possible.

Specific solution . With $N = 2018$ this means that $N_1 = N_2 = 504$ and $N_3 = N_4 = 505$ , so that $X = 2\binom{504}2 + 2\binom{505}2 = 504\cdot 503 + 505\cdot 504 = (503 + 505)\cdot 504 = \boxed{508\,032}.$

General solution . Writing $N = 4q + r$ with $0 \leq r < 4$ , this means that we have $r$ bins of size $q + 1$ and $4 - r$ bins of size $q$ , and $X = \tfrac12q(q+1)r + \tfrac12(q-1)q(4-r) = \tfrac12q(4q + 2r - 4) = \frac12q(N + r - 4).$ In the case $N = 2018$ we have $q = 504$ and $r = 2$ , so that $X = \tfrac12\cdot 504\cdot (2018 + 2 - 4) = \boxed{508\,032}.$

---

Note that for large values of $N$ , the minimum number of pairs with lattice midpoints tends to $\tfrac 1 4$ of the total number of pairs.

---

Proof that the value is minimal if the $N_i$ are chosen as similar as possible: suppose that $N_j > N_i$ . Remove a point from bin $S_j$ and add a points to bin $S_i$ . Then the number of lattice midpoints they contribute changes by $\Delta X = \left[\tfrac12(N_j-1)(N_j-2) + \tfrac12(N_i+1)N_i\right] - \left[\tfrac12N_j(N_j-1) + \tfrac12N_i(N_i - 1)\right] = N_i-(N_j-1) = 1 - (N_j-N_i).$ This is negative if $N_j > N_i + 1$ . Therefore we can always reduce the value of $X$ by reducing the number of points in the larger bins and increasing the number of points in the smaller bins until they differ no more than one from each other.