Codeforces #183 Div1. B. Rectangle Puzzle II

さてB。ここらへんまでは危なげなくクリアしている。
http://codeforces.com/contest/303/problem/B

問題

二次元座標上で(0,0)-(N,M)の領域を考える。
この領域中で座標(X,Y)が与えられる。
この領域中に辺がX軸とY軸に平行な長方形のうち、幅と高さの比率がA,Bの長方形で面積が最大のもののうち、(X,Y)が長方形の中心に最も近く、その中で座標が辞書順で最も小さい物を返せ。

解法

比率A,Bはまず最大公約数で割って既約にしておく。
D = min(N/A,M/B)とすると、大きさが(A*D,B*D)の長方形が面積が最大となる。
次にこの長方形の中心が(X,Y)に近くなるよう配置する。

本番はえらい無駄なコードを書いてしまったが、後で見たらもっと簡単に書けた。

Xが(A*D/2)～(N-A*D/2)の間にあれば、その点を中心と出来る。
その外側にあれば、(A*D/2)または(N-A*D/2)を中心と出来る。
Y座標についても同様。

ll N,M,X,Y,A,B;
ll gcd(ll a, ll b) { return (b==0)?a:gcd(b,a%b);}

void solve() {
	int f,r,i,j,k,l,x,y;
	
	cin>>N>>M>>X>>Y>>A>>B;
	ll g=gcd(A,B);
	A/=g;
	B/=g;
	
	ll MD=min(N/A,M/B);
	N*=2;M*=2;X*=2;Y*=2;
	
	ll x1=min(max(X,MD*A),N-MD*A)-MD*A;
	ll y1=min(max(Y,MD*B),M-MD*B)-MD*B;
	_P("%lld %lld %lld %lld\n",x1/2,y1/2,x1/2+MD*A,y1/2+MD*B);
	
	return;
}

まとめ

最初与えられた点を中心にしないといけないと勘違いして時間をロスした。