SRM614 Div1Easy MinimumSquare

SRM

問題概要
K個以上の座標を完全に包含できる正方形の最小面積を求めよ。

制約

  • 座標の要素数：2〜100個
  • -10^9 <= x, y <= 10^9

解法
与えられた座標のうち「『1点の座標(X, Y)』または『2点の x, y それぞれの min を取った座標(X, Y)』」から一回り大きい座標(X-1, Y-1) を始点として、一辺を二分探索する。

計算量は N^3 * log(10^9) = N^3 * 30 = 10^6 * 30 くらい。

using namespace std;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
class MinimumSquare {
public:
  ll minArea(vector <int> x, vector <int> y, int K) {
    int N = x.size();
    const ll MXSIZE = max(*max_element(ALL(x))+1 - (*min_element(ALL(x))-1),
                          *max_element(ALL(y))+1 - (*min_element(ALL(y))-1));
    ll ans = MXSIZE;
    rep(i, N) REP(j, i, N) {
      ll sx = min(x[i]-1, x[j]-1), sy = min(y[i]-1, y[j]-1);
      ll L = 1, R = MXSIZE+1;
      while(R-L > 1) {
        ll M = (L+R) / 2;
        int cnt = 0;
        rep(k, N) {
          cnt += (sx < x[k] && x[k] < sx + M) && (sy < y[k] && y[k] < sy + M);
        }
        if(cnt < K) {
          L = M;
        }
        else {
          R = M;
        }
      }
      ans = min(ans, R);
    }
    return ans*ans;
  }
};