TopCoder SRM 607, Division 2, Level 1 : BoundingBox

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12990&rd=15840

問題概要

　平面上の整数座標にいくつかの点がある。辺がいずれかの座標軸に並行な長方形であって、与えられた点を全て内部（辺上を含む）にもつようなもののうち、面積が最小となるものの面積を求めよ。

解法

　X 座標について考えると、全ての点は X 座標が [ min( X ), max( X ) ] の範囲内であるような領域の内部にあります。これより狭い区間では点が外部に出てしまいますし、広い区間にすることは無駄です。Y 座標についても同じことが言え、全ての点は [ min( Y ), max( Y ) ] であるような領域の内部にあります。これら二つの領域の共通部分が求めるべき長方形です。長方形の幅は明らかに max( X ) - min( X ) であり、高さは max( Y ) - min( Y ) です。従って、( max( X ) - min( X ) ) * ( max( Y ) - min( Y ) ) が問題の答えです。

コード

#define ALL( c ) (c).begin(), (c).end()

#define fst first
#define snd second

class BoundingBox
{
public:
	int smallestArea( vector <int> X, vector <int> Y )
	{
		const auto hor = minmax_element( ALL( X ) );
		const auto ver = minmax_element( ALL( Y ) );
		return abs( *hor.fst - *hor.snd ) * abs( *ver.fst - *ver.snd );
	}
}