TopCoder SRM614 DIV1 EASY - MinimumSquare

Source

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)))$.
座標の値が大きいのでオーバーフローに注意する.

C++によるスパゲッティなソースコード

// #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)

ログイン: