SRM614 Div1 Easy "MinimumSquare"
問題
TopCoder Statistics - Problem Statement
訳
平面上にN個の点がある。あなたはN個の要素を持つint[] x, yが与えられる。N個の点の座標は(x[0],y[0]), (x[1],y[1]), ..., (x[N-1],y[N-1]).となる。
あなたは1つの正方形をその平面上に書こうとしている。その正方形の頂点は整数であり、x軸・y軸に平行なものである。さらに1つ制約があり、N個の点のうち、K個以上を正方形の内部に含めないといけない。(ただし、辺と重なる点は数えない。)
あなたはx, yそしてint Kが与えられるので、上記の制約を満たす正方形の最小の面積を返せ。
制約
2 <= N <= 100
-10^9 <= x[i], y[i] <= 10^9
1 <= K <= N
考えたこと
題意で求められている正方形の頂点は、必ず(x[i] - 1, y[i] - 1), (x[i] + 1, y[i] - 1), (x[i] - 1, y[i] + 1), (x[i] + 1, y[i] + 1)を含むはずだから、2点を決め打ちして全探索すればよい。全探索にO(N^2)、内包する点の数を数え上げるのにO(N)、全体でO(N^3)で解ける。余裕。そして撃墜。
赤い人のソースコード
題意で求められている正方形の左下の頂点を決め打ちする。候補となるのは(x[i] - 1, y[j] - 1)(x, yは任意)となり、これで全探索すればよい。左下の頂点を決めたら、そこから右上方向に正方形を伸ばしていって、K個の点が内包できた時点で面積を出して最小をとっていく。
ソースコード
class MinimumSquare { public: long long minArea(vector <int> x, vector <int> y, int K) { int n = x.size(); long long best = (long long)pow(10, 10); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int x1 = x[i]; int y1 = y[j]; vector<long long> r; for (int k = 0; k < n; k++) { if (x1 <= x[k] && y1 <= y[k]) r.push_back(max(x[k] - x1, y[k] - y1)); } if (K <= r.size()) { sort(r.begin(), r.end()); best = min(best, r[K - 1]); } } } return (best + 2) * (best + 2); } };