WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #183 Div2 D "Rectangle Puzzle II"

問題

http://codeforces.com/contest/304/problem/D

あなたには四角形のグリッドが与えられる。そのグリッドのサイズはn * mである。グリッドにおける位置を座標系で表す事にする。グリッドの各ポイントは(x, y)という整数のペアの座標となる。

あなたの課題はグリッド上にポイント(x, y)を含み、長さの比が(a, b)である、最も大きい四角形(x1, y1, x2, y2)を見つける事である。
この条件を言い換えれば、
0 <= x1 <= x <= x2 <= n
0 <= y1 <= y <= y2 <= m
(x2 - x1) / (y2 - y1) = a / b
を満たすことである。

この四角形の辺は軸に平行でなければならず、x1, y1, x2, y2は整数である事が求められる。

もし解答が複数あるのならば、その中で(x, y)をclosestな四角形を見つけよ。"closestである"とは四角形の中心と、(x, y)のユークリッド距離が最も小さいものである、ということである。まだ複数個の候補があるのなら、辞書順で最小のものを見つけよ。"辞書順で最小のものである"とは(x1, y1, x2, y2)を辞書順で並べて、その最小のものである、ということである。

制約

1 <= n, m <= 10^9
1 <= x, a <= n
1 <= y, b <= m


考えた事

うーん やるだけっちゃーやるだけ?


ソースコード

typedef long long I64;

I64 gcd( I64 a, I64 b ){
    if( a < b ) swap( a, b );
    if( a % b == 0 ) return b;
    return gcd( b, a % b );
}

int main() {
    I64 n, m, x, y, a, b;
    cin >> n >> m >> x >> y >> a >> b;

    int d = gcd( a, b );
    a /= d; b /= d;

    // 最も大きいものを出す
    I64 w = n / a * a;
    I64 h = m / b * b;
    h = min( w / a * b, h ); // intだとここらでオーバーフローする可能性あり!!
    w = h / b * a;

    // closestで辞書順で最小のものを出す
    I64 sx = max( 0LL, x - (w+1) / 2 );
    sx = min( sx, n - w );
    I64 sy = max( 0LL, y - (h+1) / 2 );
    sy = min( sy, m - h );

    I64 ex = sx + w;
    I64 ey = sy + h;

    printf( "%I64d %I64d %I64d %I64d\n", sx, sy, ex, ey );
}