Vasya and Triangle [Codeforces Round #512 (Div. 1, based on Technocup 2019 Elimination Round 1) A]

http://codeforces.com/contest/1053/problem/A

x座標が[0,N]の間、y座標が[0,M]の間にある異なる格子点を3つとって、面積をNM/Kにせよ。
存在しないならNO

考察過程

1. K=2の時に最大で、(0,0), (0,M), (N,0)の三角形
2. 例えばK=3を作りたいときは、この面積×2/3をすればいい
3. ×2/3を達成するには、最大の三角形のどちらかの辺を×2/3すればできる
4. それ以外に魅力的な方針がみつからないので、祈りながら出すと通る

解法

http://codeforces.com/contest/1053/submission/43302652

K=2の時の最大の三角形を変形していく方針で解く。
以降、W=N, H=Mとして説明していく。
Kが偶数、奇数で処理を分ける。
　
Kが偶数のときは、最大の三角形×2/Kとしたときに、2/Kが約分できる。
つまり、×1/K'を実現できるか考える。
横と縦をそれぞれ、×1/x, ×1/yにしたとする。
この時満たすべき条件は、

• xはWの約数
• yはHの約数
• xy=K'

K'は確定しているので、xを全探索すればyが決定する。
よって、予めWの約数を全列挙しておき、xを全探索しよう。
すべての条件を満たすものがあったら、縦横*1/x,*1/yして答える。
　
Kが奇数のときも、基本方針は同じ。
×2/Kを実現することを考えるが、まずは×1/Kが実現できるか確認しよう。
満たす、x,yが見つかったら、×2/x, ×1/yの場合か×1/x, ×2/yの場合のどちらかができないか確かめる。
できれば、それを答える。

int W, H, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> W >> H >> K;
    auto ed = enumdiv(W);

    if (K % 2 == 0) {
        K /= 2;
        fore(x, ed) {
            if (0 < K % x) continue;
            int y = K / x;
            if (0 < H % y) continue;

            printf("YES\n");
            printf("0 0\n");
            printf("0 %d\n", H / y);
            printf("%d 0\n", W / x);
            return;
        }
    } else {
        fore(x, ed) {
            if (0 < K % x) continue;
            int y = K / x;
            if (0 < H % y) continue;

            int yy = H / y;
            int xx = W / x;

            if (1 < y) yy *= 2;
            else if (1 < x) xx *= 2;
            else continue;

            printf("YES\n");
            printf("0 0\n");
            printf("0 %d\n", yy);
            printf("%d 0\n", xx);
            return;
        }
    }

    printf("NO\n");
}