TopCoder SRM 614, Division 2, Level 2 : MinimumSquareEasy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12982&rd=15847

問題概要

　平面上に N 個の点がある。この平面上の正方形であって、次の condition を満たすものの内で面積が最小のものを求め、その面積を出力せよ。

• 角は整数座標にある
• 辺はいずれかの座標軸に並行
• 与えられた点集合の内、N - 2 個以上をその内部（辺上は含まない）に含む

解法

　正方形の外部になる点が高々 2 個と少ないので、外部に出る点の組み合わせを全通り試しても 個しかありません。外部に出る点が決まると同時に、内部に入る点の集合が決まります。正方形内部に入るべき点の集合が決まれば、X 座標・Y 座標の最小値・最大値を求めることで、それらの点を内包する最小の長方形領域を求めることができます。問題が要求しているのは正方形領域の面積なので、こうして求まる長方形の幅・高さの内、長い方の長さを二乗した値が解候補となります。解候補の内最小のものが問題の答えです。

コード

using LL = long long;
template < typename T = int > using LIM = numeric_limits<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int INF = LIM<>::max();

class MinimumSquareEasy
{
public:
	long long minArea( vector <int> x, vector <int> y )
	{
		const int N = x.size();

		LL res = LIM<LL>::max();
		REP( i, 0, N )
		{
			REP( j, 0, i )
			{
				int minx = INF, maxx = -INF, miny = INF, maxy = -INF;
				REP( k, 0, N )
				{
					if ( k == i || k == j )
					{
						continue;
					}
					minx = min( minx, x[k] );
					maxx = max( maxx, x[k] );
					miny = min( miny, y[k] );
					maxy = max( maxy, y[k] );
				}
				const LL l = max( maxx - minx, maxy - miny ) + 2;
				res = min( res, l * l );
			}
		}

		return res;
	}
};