kmjp's blog

競技プログラミング参加記です

Codeforces #239 Div1 A. Triangle

CF239に参加。
A,Bを解いたものの両方ミス、まさかの0点…と思ったらAで15Hackを決めそれだけで2ケタ順位に入るというグダグダっぷり。
http://codeforces.com/contest/407/problem/A

問題

2つの整数a,bが与えられる。
以下の条件を満たす2次元座標中の格子点3つがあれば答えよ。

  • 3点は直角三角形を成し、直角を挟む2辺の長さはa,bである。
  • 各辺はX軸およびY軸に平行でない。

解法

1つの点を原点に置くとする。
そこからの長さがa,bとなるような座標(ax,ay),(bx,by)(それぞれ正の整数)を総当たりで求める。

両者のX軸と成す角が同じであったら、片方90度回転させればよい。
その際、X座標同士やY座標同士が一致しないよう気を付ける必要がある。

おかげで、a=15,b=20の時(12,9)(12,-16)といった回答が多数あり、15hack取ることができた。

int A,B;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>A>>B;
	
	int ax,bx;
	for(ax=1;ax<A;ax++) {
		int ay=sqrt(A*A-ax*ax+0.5);
		if(ax*ax+ay*ay!=A*A) continue;
		for(bx=1;bx<B;bx++) {
			int by=sqrt(B*B-bx*bx+0.5);
			if(bx*bx+by*by!=B*B) continue;
			
			if(ax*by==ay*bx) {
				_P("YES\n");
				_P("0 0\n");
				_P("%d %d\n",ax,ay);
				if(ay==bx) _P("%d %d\n",by,-bx);
				else _P("%d %d\n",-by,bx);
				return;
			}
		}
	}
	_P("NO\n");
}

まとめ

自分が解けなかったのにHackだけこんなにとれるとは。

広告を非表示にする