欧拉线上包含了外心、垂心、重心和九点圆的圆心，其中重心的坐标是容易求的：$G=\frac{A+B+C}{3}$。将重心的坐标带入直线的表达式得到 $$ k(A_x+B_x+C_x)+l(A_y+B_y+C_y)+3m=0 $$ 由于坐标是整数，我们能够立刻得到一个必要条件：$\gcd(k,l)\mid 3m$。接下来我们给出对于满足上述条件的任意情况的构造。

构造的思路是从一些已知的三角形和其欧拉线出发，通过相似变换，也就是旋转、缩放和平移，最终得到想要的直线。

为了保证坐标仍然是整数，我们希望最终的变换是以下的形式：

• 先乘上矩阵 $M=\begin{pmatrix}p&-q\\q&p\end{pmatrix}$，其中 $p,q$ 是整数且 $p^2+q^2\ne 0$。这个 $M$ 表示旋转和缩放（考虑一般的旋转形如 $R_\theta=\begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix}$）。
• 然后平移 $(t_x,t_y)$。

我们希望从简单的直线，例如 $3x+r=0\pod{r=0,1,2}$ 出发，通过上述变换得到想要的直线。带入上面变换的结果，我们得到这个直线的方程应该是 $$ k(px-qy+t_x)+l(qx+py+t_y)+m=0 $$ 化简一下得到 $$ (kp+lq)x+(lp-kq)y+(kt_x+lt_y+m)=0 $$ 对比系数，可以列出方程 $$ kp+lq=3a\\ lp-kq=0\\ kt_x+lt_y+m=ra $$ 令 $g=\gcd(k,l),p=\frac{k}{g},q=\frac{l}{g}$，则第二个方程能够满足，第一个方程可以解出 $a=\frac{(p^2+q^2)g}{3}$。第三个方程化为 $$ 3pt_x+3qt_y+\frac{3m}{g}=(p^2+q^2)r $$ 我们只需要选择合适的 $r$ 使得 $(p^2+q^2)r-\frac{3m}{g}\equiv 0\mod 3$，然后再选择合适的 $t_x,t_y$ 即可。而因为 $\gcd(p,q)=1$，所以 $p^2+q^2\not\equiv0\mod 3$，因此一定存在这样的 $r$。

最后还有两个细节需要处理：

• 找到欧拉线为 $3x+r=0$ 的三角形：只需要枚举所有坐标小的情况并检验即可。
• 坐标范围：假设基础三角形坐标范围是 $O(1)$，乘上矩阵 $M$ 之后的坐标范围则是 $O(p+q)$；平移的时候找到合适的 $t_x,t_y$，例如当 $|p|>|q|$ 时优先让 $t_y$ 的绝对值尽可能小，可以使得最终的坐标范围是 $O(|k|+|l|+|m|)$。