\((0,0),(0,1),(1,0),(1,1)\) の正方形を含む三角形は、三角形の頂点の座標の絶対値をの最大値を \(M\) とし、面積を \(\frac{S}{2}\) として、 \(M\leq S\) が成り立ちます。

よって、 \(S\) が小さい場合は全探索することが可能です。

全探索することで、 \(S=1,2,3,5,7\) のときは良い三角形が存在しないことが確認できます。

\(S=4\) のときは、サンプルにもあるように、良い三角形が存在します。

その他の \(S\) については以下の方法で構築することができる良い三角形が存在します。

互いに素な \(2\) 以上の正整数 \(p,q\) について、以下の条件を満たす正整数 \(s,t\) が存在します。

• \(1\leq s\lt p\)
• \(1\leq t\lt q\)
• \(sq-tp=1\)

このような \(p,q,s,t\) を用いると、\((0,0),(p,q),(s+1,t-1)\) を頂点とする三角形は、面積が \(\frac{p+q+1}{2}\) の良い三角形となります。

面積については、 \((s+1)q-(t-1)p=sq-tp+q+p=1+p+q\) より成り立ちます。

三角形の中には \((s,t),(s+1,t-1)\) が対角線の正方形が含まれています。

三角形の中に含まれる格子点のうち、 \((0,0),(p,q)\) を結ぶ直線に最も近いのは、 \((0,0),(p,q)\) を除くと \((s,t)\) のただひとつで、最も遠いのは \((s+1,t-1)\) ただひとつです。

\((1,-1),(p+1,q-1)\) が三角形に含まれていないことから、 \((a,b),(a+1,b-1)\) をどちらも含む整数の組 \((a,b)\) は \((s,t)\) のみです。

よって、\((s,t),(s+1,t-1)\) が対角線の正方形以外に正方形は含まれていません。

\(S=p+q+1\) を満たす \(p,q\) をひとつ見つけることができれば、ユークリッドの互除法より \(s,t\) を見つけられるので、良い三角形を出力できます。

\(p=2,3,\dots \) の順に、 \(p\) と \(q=S-p-1\) が互いに素であるか確認すれば良いです。

\(1\) つのテストケースに対して、時間計算量 \(O(\log(S))\) で求めることができます。

また、 \(8\) の倍数で場合分けや \(2\) の倍数で場合分けすることで \(O(1)\) で解くことができます。