WARush

SRMの結果とか、解けた問題のコードを書いていきます

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);    
    }
};