読者です 読者をやめる 読者になる 読者になる

SRM 614 Div2 Medium MinimumSquareEasy

問題

SRM 614 - TopCoder Wiki

N個の2次元平面上の点が与えられる. これらのうちN-2の点を完全に内包する正方形を考える. そのような正方形の最小面積を求める問題.

解答

N-2の選び方は,何を選ばないかということと同じなので, 選ばない点を求め,最小面積を計算. そのような組はO(n2)ある.

当初正方形という条件を見落としていて,結果が合わなかった...

class MinimumSquareEasy
{
public:
  long long minArea(vector <int> x, vector <int> y)
    {
      int n = x.size();
      int i, j, ii, jj;
      long long inf = LONG_MAX;
      long long res = inf;
      for (i = 0; i < n; i++){
        for (j = i+1; j < n; j++) {
          long long minx=inf;
          long long maxx = -inf;
          long long miny=inf;
          long long maxy = -inf;
          for (ii = 0 ; ii < n; ii++){
            if (ii != i && ii != j) {
              minx = min(minx, (long long) x[ii]);
              maxx = max(maxx, (long long) x[ii]);
              miny = min(miny, (long long) y[ii]);
              maxy = max(maxy, (long long) y[ii]);
            }
          }
          long long len = max((maxx - minx + 2), (maxy - miny + 2));
          res = min(res, len * len);
        }
      }
      return res;
    }
};