Detailed mathematical approach

Problem Summary

The ellipse in the problem is the locus of points \(Q\) such that \(QM+QG=15000\), where the foci are \(M=(-2000,1500)\) and \(G=(8000,1500)\). For an integer lattice point \(P\) outside that ellipse, two tangents can be drawn from \(P\) to the ellipse. We must count the lattice points for which the angle between those two tangent rays is greater than \(45^\circ\).

A naive geometric search would be awkward because every candidate point would seem to require solving for the tangency points. The implementations avoid that completely. They translate the ellipse to its center, derive a closed inequality for the tangent angle, and then count lattice points column by column.

Mathematical Approach

Let \((X,Y)\) be the original coordinates, and shift to centered coordinates

$x=X-3000,\qquad y=Y-1500.$

The midpoint of the two foci is \((3000,1500)\), so after translation the foci become \((\pm 5000,0)\). The lattice is unchanged because the shift vector is integral.

Standard Form of the Ellipse

The focal distance is \(2c=10000\), so \(c=5000\). The constant distance sum is \(2a=15000\), so \(a=7500\). Therefore

$b^2=a^2-c^2=7500^2-5000^2=31\,250\,000.$

The ellipse is thus

$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1,\qquad a^2=56\,250\,000,\qquad b^2=31\,250\,000.$

All later formulas depend only on these centered quantities.

Exterior Points and the First Column Bound

Two real tangents exist only when the point lies strictly outside the ellipse. In centered coordinates this means

$\frac{x^2}{a^2}+\frac{y^2}{b^2} \gt 1,$

or equivalently

$b^2x^2+a^2y^2 \gt a^2b^2.$

For a fixed nonnegative \(x\), this gives the lower edge of the admissible vertical column. If \(x^2\gt a^2\), then \(y=0\) is already outside the ellipse. If \(x^2\le a^2\), then we need

$y^2 \gt \frac{a^2b^2-b^2x^2}{a^2},$

so the first valid integer \(y\) is the smallest integer strictly above that threshold.

Deriving the Tangent-Angle Formula

Take an exterior point \(P=(x_0,y_0)\). A line through \(P\) with slope \(m\) has equation \(y=mx+c\), where \(c=y_0-mx_0\). Such a line is tangent to the ellipse exactly when

$c^2=a^2m^2+b^2.$

Substituting \(c=y_0-mx_0\) gives a quadratic equation for the two tangent slopes:

$\left(x_0^2-a^2\right)m^2-2x_0y_0m+\left(y_0^2-b^2\right)=0.$

If the roots are \(m_1\) and \(m_2\), then

$m_1+m_2=\frac{2x_0y_0}{x_0^2-a^2},\qquad m_1m_2=\frac{y_0^2-b^2}{x_0^2-a^2}.$

The angle \(\theta\) between the two tangent rays satisfies

$\tan^2\theta=\frac{(m_1-m_2)^2}{(1+m_1m_2)^2}=\frac{4\left(b^2x_0^2+a^2y_0^2-a^2b^2\right)}{\left(x_0^2+y_0^2-a^2-b^2\right)^2}.$

This identity is the central geometric formula used in all three implementations.

The Director Circle and the \(45^\circ\) Test

The denominator vanishes on

$x^2+y^2=a^2+b^2,$

the director circle of the ellipse. On this circle the two tangents are perpendicular. That gives a clean case split.

If a point is outside the ellipse but satisfies \(x^2+y^2\le a^2+b^2\), then the tangent angle is at least \(90^\circ\), so it automatically exceeds \(45^\circ\).

If \(x^2+y^2\gt a^2+b^2\), then \(0\lt\theta\le 90^\circ\), so the problem condition is equivalent to \(\tan\theta\gt 1\). Using the previous formula yields

$4\left(b^2x^2+a^2y^2-a^2b^2\right)-\left(a^2+b^2-x^2-y^2\right)^2 \gt 0.$

This polynomial inequality is exactly the test performed by the implementations.

Reducing the Count to One Quadrant

The ellipse, the exterior condition, and the angle inequality all depend only on \(x^2\) and \(y^2\). Therefore the valid set is symmetric under reflections across both coordinate axes. It is enough to count the centered lattice points with \(x\ge 0\) and \(y\ge 0\), then correct for axis overcounting.

Counting a Fixed \(x\)-Column

For one nonnegative integer \(x\), the admissible \(y\)-values form a contiguous interval beginning at the first point outside the ellipse.

The first portion of that interval is automatic: every integer

$y_{\min}(x)\le y\le \left\lfloor\sqrt{a^2+b^2-x^2}\right\rfloor$

qualifies whenever it lies between the ellipse and the director circle.

Beyond the director circle, set \(u=y^2\) and write

$k=a^2+b^2-x^2.$

Then the angle condition becomes

$-u^2+(4a^2+2k)u+4\left(b^2x^2-a^2b^2\right)-k^2 \gt 0.$

This is a downward-opening quadratic in \(u\), so the valid values are exactly those below its larger root. Hence

$u_{\max}(x)=\frac{4a^2+2k+\sqrt{(4a^2+2k)^2+4\left(4\left(b^2x^2-a^2b^2\right)-k^2\right)}}{2},$

and the largest admissible integer \(y\) is \(\lfloor\sqrt{u_{\max}(x)}\rfloor\), adjusted by a tiny integer correction because the inequality is strict.

Worked Example: Why the Search Is Finite

Take the \(x\)-axis, so \(y=0\). Being outside the ellipse means \(x^2\gt a^2\). Set

$z=x^2-a^2.$

The \(45^\circ\) inequality becomes

$4b^2z \gt (b^2-z)^2,$

which simplifies to

$z^2-6b^2z+b^4 \lt 0.$

Therefore

$b^2(3-2\sqrt{2}) \lt z \lt b^2(3+2\sqrt{2}).$

In particular, every qualifying axis point satisfies \(z\lt 6b^2\), so

$x^2 \lt a^2+6b^2.$

The same argument on the \(y\)-axis gives \(y^2\lt b^2+6a^2\). This is why the code only scans finitely many columns and rows, using those rounded-up bounds as safe limits.

How the Code Works

Geometric Precomputation

The C++, Python, and Java implementations first reduce the problem data to \(a^2\), \(b^2\), \(a^2+b^2\), and \(a^2b^2\). Once those are known, every geometric decision becomes an integer comparison in centered coordinates.

Column-by-Column Counting

For each nonnegative integer \(x\), the implementation computes the first integer \(y\) outside the ellipse. It then counts every point up to the director circle immediately, because those points satisfy the angle condition automatically. If the column extends beyond the director circle, it solves the quadratic inequality in \(u=y^2\) to obtain the last admissible \(y\) in that column and adds the remaining points.

No tangent points are ever constructed explicitly. The algorithm works entirely with the derived inequalities, which is why it stays fast and numerically stable.

Exact Integer Arithmetic and Symmetry Repair

The implementations use integer square roots and exact integer comparisons, then make short upward or downward corrections when a strict inequality sits just past the square-root estimate. That avoids off-by-one errors near the boundary.

If \(N_{Q1}\) is the number of qualifying centered lattice points with \(x\ge 0\) and \(y\ge 0\), then the full answer is reconstructed as

$N=4N_{Q1}-2N_x-2N_y+N_0,$

where \(N_x\) and \(N_y\) count the qualifying points on the centered axes and \(N_0\) is the origin correction. The C++ and Java implementations parallelize the column sweep, while the Python implementation applies the same mathematics with a serial or process-based split depending on the runtime environment.

Complexity Analysis

Let \(X_{\max}\) be the safe horizontal scan bound, which is on the order of \(\sqrt{a^2+6b^2}\). The main loop processes each integer \(x\) from \(0\) to \(X_{\max}\), and each column requires only constant-time arithmetic plus a few final boundary corrections. The running time is therefore essentially linear in the scanned width.

Memory usage is \(O(1)\) beyond a handful of counters and geometric constants, or \(O(T)\) if one includes thread-local accumulators for \(T\) workers. The important point is that the algorithm never searches over tangent points on the ellipse; it counts lattice points directly from closed formulas.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=246
2. Ellipse: Wikipedia - Ellipse
3. Director circle: Wikipedia - Director circle
4. Tangent: Wikipedia - Tangent
5. Quadratic equation: Wikipedia - Quadratic equation