TopCoder SRM614 DIV1 EASY (250pt)
Problem Statement
2次元平面上に $N$ 個の点 $(X_k, Y_k)$ が与えられる.
厳密に内部に $K$ 個以上の点を含み,頂点が格子点で,各辺が $x$ 軸か $y$ 軸に平行な正方形の中で,面積最小のものの面積を求める問題.
解き方は色々ある.
例えば,長方形で囲むことを考えて,後で,長い方の辺に合わすとする.
$y$ 座標の値で点をソートしておく.
右端と左端($x$ 座標側)を全部試す.(各点の $x$ 座標の $\pm 1$ だけ試せば良い)
その $x$ 座標に入っている点を列挙して,それらの点のうち,$K$ 個先の点との $y$ 座標の差の最小値を求めれば,長方形の縦の長さの最小値が求まる.
これは$O(N^3)$.
他の方法としては,正方形の辺の長さを二分探索し,左下の座標を全部試す,などの方法もある.$O(N^3 \log (\max(X_k,Y_k)))$.
座標の値が大きいのでオーバーフローに注意する.
// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ll long long
class MinimumSquare {
public:
ll minArea(vector <int> x__, vector <int> y__, int K) {
int i, j, k, n;
int x1, x2;
pair<int,int> hoge[1000];
ll x[1000], y[1000];
ll ok[1000], ok_size;
ll res = 2000000100, tmp, tmp2;
res *= 2000000100;
n = x__.size();
rep(i,n) hoge[i] = make_pair(y__[i], x__[i]);
sort(hoge, hoge+n);
rep(i,n) y[i] = hoge[i].first, x[i] = hoge[i].second;
rep(x1,n) rep(x2,n) if(x[x1]<=x[x2]){
ok_size = 0;
rep(i,n) if(x[x1] <= x[i] && x[i] <= x[x2]){
ok[ok_size++] = y[i];
}
tmp = x[x2] - x[x1] + 2;
REP(i,K-1,ok_size){
tmp2 = ok[i] - ok[i-K+1] + 2;
res = min(res, max(tmp,tmp2)*max(tmp,tmp2));
}
}
return res;
}
}
Current time: 2024年03月29日23時16分14秒
Last modified: 2014年03月31日19時14分08秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM614 SRM_Div1_Easy
トップページに戻る
Logged in as: unknown user (not login)