KUPC2015 : E - マッサージチェア2015

ちょっと苦労したけど何とか解けた。
http://kupc2015.contest.atcoder.jp/tasks/kupc2015_e

問題

W*Hの矩形が与えられる。
この内部に3点A,B,Cを取ったとき、min(AB,BC,CA)の最大値を求めよ。

解法

W≧Hとし、(0,0)-(W,H)の矩形の範囲を考える。
自分は以下の3つの最大値を取った。

• 3点を(0,0),(W,0),(W/2,H)ととる。
• 2点を対角線(0,0),(W,H)ととる。この対角線の垂直二等分線と矩形の交点を3つ目の点とする。
• 1点を(0,0)とし、あと下辺上に1点、右辺上に1点、正三角形を成すように取る。

int T;
int H,W;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		if(W<H) swap(H,W);
		double ma=min(W*1.0,sqrt(H*H+W*0.5*W*0.5));
		
		double rate=sqrt(H*H+W*W)/W;
		double aa=sqrt(H*H+W*W)/2*rate;
		ma=max(ma,aa);
		
		double t=2*W-sqrt(3)*H;
		if(t>=0 && t<=W) {
			double X=H*0.5+sqrt(3)*t/2;
			if(X>=0 && X<=H) ma=max(ma,sqrt(H*H+t*t));
		}
		
		_P("%.12lf\n",ma);
	}
}

まとめ

コード自体は短め。