SRM521 Div2 Hard

1000
それっぽい位置を正方形の角と決めて、各点が含まれるか調べる。
文字列で記憶するのが少し不安だったけど、問題なかった。

view plainprint?

1. class SquaredSubsets {  
2. public:  
3.   long long countSubsets(int n_, vector <int> x_, vector <int> y_)   
4.   {  
5.     double n = n_;  
6.     vector<double> x, y;  
7.     for (int i = 0; i < x_.size(); ++i) {  
8.       x.push_back(x_[i]);  
9.       y.push_back(y_[i]);  
10.     }  
11.       
12.     const int N = x.size();  
13.     const double eps = 1e-4;  
14.   
15.     const int D = 9;  
16.     double dx[D] = {0, 0, 0, -eps, -eps, -eps, eps, eps, eps};  
17.     double dy[D] = {-eps, 0, eps, -eps, 0, eps, -eps, 0, eps};  
18.   
19.     set<string> P;          
20.     P.insert("");  
21.   
22.     for (int i = 0; i < N; ++i) {  
23.       for (int j = 0; j < N; ++j) {          
24.         for (int d = 0; d < D; ++d) {  
25.           const double X = x[i] + dx[d];  
26.           const double Y = y[j] + dy[d];  
27.           string a, b, c, d;  
28.           for (int k = 0; k < N; ++k) {  
29.             if (X <= x[k] && x[k] <= X + n && Y <= y[k] && y[k] <= Y + n) {  
30.               a += k + ((k < 26) ? 'A' : 'a');  
31.             }  
32.             if (X - n <= x[k] && x[k] <= X && Y - n <= y[k] && y[k] <= Y) {  
33.               b += k + ((k < 26) ? 'A' : 'a');  
34.             }  
35.             if (X <= x[k] && x[k] <= X + n && Y - n <= y[k] && y[k] <= Y) {  
36.               c += k + ((k < 26) ? 'A' : 'a');  
37.             }  
38.             if (X - n <= x[k] && x[k] <= X && Y <= y[k] && y[k] <= Y + n) {  
39.               d += k + ((k < 26) ? 'A' : 'a');  
40.             }  
41.           }  
42.           sort(a.begin(), a.end());  
43.           sort(b.begin(), b.end());  
44.           sort(c.begin(), c.end());  
45.           sort(d.begin(), d.end());  
46.           P.insert(a);  
47.           P.insert(b);  
48.           P.insert(c);  
49.           P.insert(d);  
50.         }  
51.       }  
52.     }  
53.     return (int)P.size() - 1;  
54.   }  
55.   
56. };  

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;
  }

};