torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, SRM 629, Division 2, Level 1 : RectangleCoveringEasy

問題概要

 サイズが holeH \times holeW であるような長方形の穴がある。この穴を、サイズが boardH \times boardW であるような長方形の板で塞ぐ。板は回転されて使うこともできるが、板の辺は穴の辺に並行または直角でなければならない。また、板の角は穴の外側(辺上は不可)でなければならない。穴を完全に塞ぐことができるか?

解法

 配置に関する条件から、板の置き方は、片方の辺の長さが対応する穴の辺より長くなければなりません。この条件を満たす限り、板の角が穴に落ちることはありせん。このように配置して、他方の辺が対応する穴の辺の長さ以上の長さをもつならば、穴は完全に塞がれています。
 板を配置する向きは二通りしか無いので、全部試して条件を満たすものが存在するかを調べれば解くことができます。

コード

class RectangleCoveringEasy
{
public:
	int solve( int holeH, int holeW, int boardH, int boardW )
	{
		return f( holeH, holeW, boardH, boardW ) || f( holeW, holeH, boardH, boardW ) ? 1 : -1;
	}

	bool f( const int a, const int b, const int c, const int d )
	{
		return a < c && b <= d || b < d && a <= c;
	}
};