POJ.2836 Rectangular Covering

1.Problem
http://poj.org/problem?id=2836

2.Idea
bit DP

3.Source

 struct Rect {  
      int x, y;  
      int w, h;  
      int mask;  
      bool contain(int qx, int qy) {  
           if (qx < x || qx > x + w) return false;  
           if (qy < y || qy > y + h) return false;  
           return true;  
      }  
      int area() const {  
           return w * h;  
      }  
 };  
 #define MAX_N 15  
 const int INF = 0x3f3f3f3f;  
 int x[MAX_N], y[MAX_N];  
 vector<Rect> rects;  
 int n;  
 int dp[1 << MAX_N];  
 void makeRect(int i, int j)  
 {  
      Rect rec;  
      rec.x = min(x[i], x[j]);  
      rec.y = min(y[i], y[j]);  
      rec.w = max(1, max(x[i], x[j]) - rec.x);  
      rec.h = max(1, max(y[i], y[j]) - rec.y);  
      rec.mask = 0;  
      for (int i = 0; i < n; i++) {  
           if (rec.contain(x[i], y[i])) {  
                rec.mask |= (1 << i);  
           }  
      }  
      rects.push_back(rec);  
 }  
 int main()  
 {  
      while (cin >> n) {  
           if (n == 0) break;  
           memset(dp, INF, sizeof(dp));  
           rects.clear();  
           for (int i = 0; i < n; i++) {  
                cin >> x[i] >> y[i];  
           }  
           for (int i = 0; i < n; i++) {  
                for (int j = i + 1; j < n; j++) {  
                     makeRect(i, j);  
                }  
           }  
           fill(dp, dp + MAX_N, INF);  
           dp[0] = 0;  
           for (int S = 0; S < (1 << n); S++) {  
                if (dp[S] != INF) {  
                     for (int k = 0; k < rects.size(); k++) {  
                          if (S != (S | rects[k].mask)) {  
                               dp[S | rects[k].mask] = min(dp[S | rects[k].mask], dp[S] + rects[k].area());  
                          }  
                     }  
                }  
           }  
           printf("%d\n", dp[(1 << n) - 1]);  
      }  
      return 0;  
 }