Solution:

Let $g = \gcd(n, m)$, with $n = g \cdot a$ and $m = g \cdot b$. Note that the number of points on the diagonal of $R$ connecting $(0,0)$ and $(n, m)$ is $g+1$.

We construct two far-reaching quadrilaterals and show that at least one of them has small area.

For our first quadrilateral, let $(x_1, y_1)$ and $(x_2, y_2)$ be the points with the shortest nonzero distances to the diagonal between $(0,0)$ and $(n, m)$ which lie above and below the diagonal, respectively. Now consider the quadrilateral with vertices $(0,0)$, $(x_1, y_1)$, $(n, m)$, $(x_2, y_2)$. Note that the only lattice points which can lie on or inside this quadrilateral are $(x_1, y_1)$, $(x_2, y_2)$, and points on the diagonal of $R$, as otherwise we could find a closer point to the diagonal than $(x_1, y_1)$ and $(x_2, y_2)$. Thus by Pick's Theorem, the area of this quadrilateral is at most $g$.

For our second quadrilateral, we will take as our vertices the points $(0,0)$, $(n-1, m)$, $(a, b)$, and $(n, m-1)$. This is a concave quadrilateral which can be split into two triangles of areas $\frac{a}{2}$ and $\frac{b}{2}$, so the area of this quadrilateral is at most $\frac{1}{2}(a+b)$.

We have therefore shown that there is always a far-reaching quadrilateral with area at most $\min\left(g, \frac{1}{2}(a+b)\right)$. Since $g \cdot \frac{1}{2}(a+b) = \frac{1}{2}(n+m) \leq 10^{10}$, we have that $\min\left(g, \frac{1}{2}(a+b)\right) \leq 10^{5}$, so we can always find a far-reaching quadrilateral with area at most $10^{5}$ as desired.