POJ.1486 Sorting Slides

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

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 2222  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 int N;  
 struct Rec {  
      int xmin, xmax, ymin, ymax;  
 } Recs[50004];  
 struct Point {  
      int x, y;  
 } Points[50004];  
 bool itIncludes(int i, int j)  
 {  
      if (  Recs[i].xmin < Points[j].x && Recs[i].xmax > Points[j].x  
           && Recs[i].ymin < Points[j].y && Recs[i].ymax > Points[j].y)   
           return true;  
      else   
           return false;  
 }  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int i = 0; i < N; i++) {  
           bool update = false;  
           for (int v = 0; v < V; v++) {  
                if (!used[v] && match[v] < 0) {  
                     int cnt = 0;  
                     int u = -1;  
                     for (int j = 0; j < G[v].size(); j++) {  
                          int f = G[v][j];  
                          if (!used[f]) {  
                               u = f;  
                               cnt++;  
                          }  
                     }  
                     if (cnt == 1) {  
                          update = true;  
                          match[v] = u;  
                          match[u] = v;  
                          used[v] = true;  
                          used[u] = true;  
                          res++;  
                     }  
                }  
           }  
           if (!update) break;  
      }  
      return res;  
 }  
 void solve()  
 {  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      for (int i = 0; i < N; i++) {  
           scanf("%d%d%d%d", &Recs[i].xmin, &Recs[i].xmax, &Recs[i].ymin, &Recs[i].ymax);  
      }  
      for (int i = 0; i < N; i++) {  
           scanf("%d%d", &Points[i].x, &Points[i].y);  
      }  
      V = 2 * N;  
      for (int i = 0; i < N; i++)  
           for (int j = 0; j < N; j++) {  
                if (itIncludes(i, j)) {  
                     add_edge(i, N + j);  
                }  
           }  
      if (bipartite_matching() > 0) {  
           for (int i = 0; i < N; i++) {  
                if (match[i] > 0) {  
                     printf("(%c,%d) ", 'A' + i, match[i] - N + 1);  
                }  
           }  
           printf("\n");  
      }  
      else {  
           printf("none\n");  
      }  
 }  
 int main()  
 {  
      int t = 1;  
      while (scanf("%d", &N)>0) {  
           if (N == 0) break;  
           printf("Heap %d\n", t);  
           solve();  
           printf("\n");  
           t++;  
      }  
      return 0;  
 }