解いた問題

2/29/2012

SRM521 Div2 Hard

1000
それっぽい位置を正方形の角と決めて、各点が含まれるか調べる。
文字列で記憶するのが少し不安だったけど、問題なかった。
class SquaredSubsets {
public:
  long long countSubsets(int n_, vector <int> x_, vector <int> y_)
  {
    double n = n_;
    vector<double> x, y;
    for (int i = 0; i < x_.size(); ++i) {
      x.push_back(x_[i]);
      y.push_back(y_[i]);
    }
   
    const int N = x.size();
    const double eps = 1e-4;

    const int D = 9;
    double dx[D] = {0, 0, 0, -eps, -eps, -eps, eps, eps, eps};
    double dy[D] = {-eps, 0, eps, -eps, 0, eps, -eps, 0, eps};

    set<string> P;       
    P.insert("");

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {       
        for (int d = 0; d < D; ++d) {
          const double X = x[i] + dx[d];
          const double Y = y[j] + dy[d];
          string a, b, c, d;
          for (int k = 0; k < N; ++k) {
            if (X <= x[k] && x[k] <= X + n && Y <= y[k] && y[k] <= Y + n) {
              a += k + ((k < 26) ? 'A' : 'a');
            }
            if (X - n <= x[k] && x[k] <= X && Y - n <= y[k] && y[k] <= Y) {
              b += k + ((k < 26) ? 'A' : 'a');
            }
            if (X <= x[k] && x[k] <= X + n && Y - n <= y[k] && y[k] <= Y) {
              c += k + ((k < 26) ? 'A' : 'a');
            }
            if (X - n <= x[k] && x[k] <= X && Y <= y[k] && y[k] <= Y + n) {
              d += k + ((k < 26) ? 'A' : 'a');
            }
          }
          sort(a.begin(), a.end());
          sort(b.begin(), b.end());
          sort(c.begin(), c.end());
          sort(d.begin(), d.end());
          P.insert(a);
          P.insert(b);
          P.insert(c);
          P.insert(d);
        }
      }
    }
    return (int)P.size() - 1;
  }
};

0 件のコメント :

コメントを投稿