問題概要
平面上に N 個の点がある。この平面上の正方形領域であって、次の condition を満たすものの内で面積が最小のものを求め、その面積を出力せよ。
- 角は整数座標にある
- 辺はいずれかの座標軸に並行
- 与えられた点集合の内、K 個以上をその内部（辺上は含まない）に含む
解法
導入として計算量の大きい方法から考えていきます。まず、X, Y 座標それぞれについて、最小・最大になる点を全通り試すことを考えます。この場合、座標の差の内大きい方を二乗したものが、正方形領域の面積です。また、全ての点についてその座標を調べることで、何個の点が領域内内にあるかを数えることができます。しかしこの方法では全体で になって間に合わないので、より効率的な方法を考える必要があります。
ここで、両方の座標について最小・最大を決めるのではなく、X 座標の最小・最大だけを決めた状態を考えます。このとき、最終的に正方形領域に収まる可能性がある点は、決めた区間に収まる X 座標をもつ点のみです。そのような点のみについて考えるとすれば、これは一次元の場合に帰着できます。一次元の場合の問題を効率的に解くことができれば、始めの方法よりもよい計算量を達成することができます。
一次元の場合、点集合を座標をキーにソートしたときの、K - 1 個離れた二点によって張られる区間が解候補となります。従って、ソートに 、解候補の列挙に
かかるので、残った点から Y 座標の差の最小値を
で計算できます。
以上をまとめると、X 座標の幅を決めたとき、X 座標については仮定した両端から、Y 座標については一次元に帰着して求めることができると分かります。このようにして求まる X, Y 座標それぞれの差の内、大きい方に 2 を足して二乗したものが、解候補となる正方形領域の面積で、その内で最小の値が問題の答えです。このようにすると を達成できます。
なお、X 座標の両端を仮定するとき、初めから K 個以上の点を含むように選ぶと処理が簡単になります。
コード
using LL = long long; using VI = vector<int>; using PII = pair<int,int>; using VPII = vector< pair<int,int> >; template < typename T = int > using LIM = numeric_limits<T>; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() #define PB( n ) push_back( n ) #define fst first #define snd second class MinimumSquare { public: long long minArea( vector <int> x, vector <int> y, int K ) { const int N = x.size(); VPII ps; transform( ALL( x ), y.begin(), back_inserter( ps ), function<PII(int,int)>( make_pair<int,int> ) ); sort( ALL( ps ) ); LL res = LIM<LL>::max(); REP( i, 0, N ) { REP( j, i + K, N + 1 ) { VI ys; transform( ps.begin() + i, ps.begin() + j, back_inserter( ys ), []( const PII &a ){ return a.snd; } ); LL l = max<LL>( ps[ j - 1 ].fst - ps[i].fst, solveYs( ys, K ) ) + 2; res = min( res, l * l ); } } return res; } LL solveYs( VI &ys, const int K ) { sort( ALL( ys ) ); LL res = LIM<>::max(); REP( i, 0, ys.size() - K + 1 ) { res = min<LL>( res, ys[ i + K - 1 ] - ys[i] ); } return res; } };
