SRM614 div1 easy MinimumSquare

概要

xy座標上の点がn個与えられる。このうち少なくともk点を含むような正方形のうち面積が最小のものを求めろ。

考えたこと

x座標、y座標でそれぞれソートして小さい方からk点取る貪欲をしようとする。正方形を長方形だと誤読したりなぜか実装をバグらせたりした結果1時間くらい実装にかかる。サンプルを試すと落ちる。よくよく考えてみると貪欲が嘘。二分探索を思い浮かべ幅Xの正方形をつくることができるかの判定について考えてみる。各頂点が正方形の4隅になるパターンを試して判定するコードを実装するとサンプルが通った。提出するとシステスで落ちる。よくよく考えると二分探索の判定が嘘（4隅以外にすべきパターンが自明に存在する）。
解説記事を読むと2辺固定すればk点を貪欲に取れるのでO(n^3logn)で解けるとある。実装するとk=1のときの処理がバグっていてシステスで一回落とす。k=1で4を返すようにしたら通った。
色々難しく考えすぎて方針迷走&&実装バグらせまくりと色々ひどかった。n <= 10^5に慣れすぎてn <= 100が解けない。

学び

オーダーが大きめの解法もちゃんと思考に入れる。誤読しない。変な実装ミスをしない。

// BEGIN CUT HERE
// END CUT HERE
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a <= x && x < b)
#define MP make_pair
#define PB push_back
const int INF = (1LL << 30);
const ll LLINF = (1LL << 60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
// #define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class MinimumSquare {
public:
  long long minArea(vector<int> X, vector<int> Y, int K) {
    int n = X.size();
    if(K == 1) return 4;
    ll ret = LLONG_MAX;
    REP(i, n) FOR(j, i+1, n) {
      ll sx = min(X[i], X[j]), gx = max(X[i], X[j]);
      VL v;
      REP(k, n) if(sx<=X[k] && X[k]<=gx) v.PB(Y[k]);
      if((int)v.size() < K) continue;
      sort(ALL(v));
      ll l = LLONG_MAX;
      FOR(k, K-1, v.size()) {
        chmin(l, v[k]-v[k-K+1]);
      }
      l+=2;
      chmax(l, gx-sx+2);
      chmin(ret, l*l);
    }
    return ret;
  }
};