問題概要

正の整数 $S$ が与えられる。次の条件を満たす三角形が存在するかどうかを判定し、存在すれ場合は 1 つ求めよ。

頂点がすべて格子点であり、座標値は $0$ 以上 $10^{8}$ 以下である
すべての頂点が格子点である面積 1 の正方形のうち、三角形の内部 (周上及び頂点を含む) に全体が含まれているものはちょうど 1 つある

(マルチテストケース)

制約

$1 \le S \le 10^{8}$

考えたこと

$S$ がある程度大きければ、ぶっちゃけ常に作れるのでは......と予想がたった。とりあえず、三角形の 1 つの頂点を原点に固定して考えることにした。

最初に考えたのは、

$(x, x+1)$ と $(x+1, x)$ で、 $S = 2x + 1$ になる (しかし、内部に正方形が含まれない)
しかし、 $(px, p(x+1))$ と $(x+1, x)$ ( $p \ge 2$ ) で、 $S = p(2x + 1)$ になる (これは内部に正方形を 1 個しか含まない)

ということだった。この時点で、 $S$ が $6$ 以上の合成数の場合はできた。

次にこの議論を膨らませることで、

$(2, 0)$ と $(p, p)$ ( $p \ge 2$ ) で、 $S = 2p$ になる
$(3, 1)$ と $(p, p+1)$ ( $p \ge 3$ ) で、 $S = 2p+3$ になる

ということがわかった。これらはいずれも内部に 1 個しか含まない。よって、 $4$ 以上の偶数と、 $9$ 以上の奇数はできた！！！

残り

この時点で、残ったのは

$S = 1, 2, 3, 5, 7$

のみとなった。これらはおそらくダメだとなった。たとえば $S = 7$ のとき、 $7$ は素数なので三角形の周上の格子点は頂点のみであるから、ピックの定理から、三角形内部の格子点の個数は 3 個となる。これと頂点とを合わせて正方形になるかというと難しそうであった。

コード

以上を実装した。とても短いコードになった。計算量は $O(1)$ である。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    long long S;
    cin >> S;
    if (S <= 3 || S == 5 || S == 7) cout << "No" << endl;
    else if (S % 2 == 0) {
        cout << "Yes" << endl;
        cout << "0 0 2 0 " << S / 2 << " " << S / 2 << endl;
    } else {
        cout << "Yes" << endl;
        cout << "0 0 3 1 " << (S - 3) / 2 << " " << (S - 1) / 2 << endl;
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}