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 ); }