#include #include #include #include //#define TEST //#define TESTOUT int xmin[30],xmax[30],ymin[30],ymax[30], xnum[30],ynum[30]; int n; bool is_in(int i, int f) { // bb of folie includes nr return (xnum[i] > xmin[f] && xnum[i]ymin[f] && ynum[i] < ymax[f]); } char int2char(int i) { return (65+i-1); } int main() { #ifndef TEST ifstream fin("slides.in"); cin = fin; #endif for (int cnt=1; 1; cnt++) { bool matrix[30][30]; for(int i=0; i<30; i++) for(int j=0; j<30; j++) matrix[i][j] = false; int res[30]; int rescnt=0; for (int i=0;i<30;i++) res[i]=0; //Input cin >> n; if (n==0) break; for (int i=1; i<=n;i++) { cin >> xmin[i] >> xmax[i] >> ymin[i] >> ymax[i]; } for (int i=1; i<=n;i++) cin >> xnum[i] >> ynum[i]; //Build Mapping for(int nr=1; nr<=n; nr++) for (int folie=1; folie <= n; folie++) { if (is_in(nr, folie)) { //map.insert(make_pair(int2char(folie),nr)); matrix[folie][nr]=true; } } // Start for (bool changed = true; changed; ){ changed = false; for (int i=1; i<=n; i++) { // Zahl nur in einer bb int foundfolie, cfolie=0; for (int zeile=1; zeile<=n; zeile++) { if (matrix[zeile][i]){ cfolie++; foundfolie = zeile; #ifdef TESTOUT printf("found %d in slide %d (%d)\n", i, zeile, cfolie); #endif } } if (cfolie==1) { #ifdef TESTOUT printf("%d is on %d\n", i, foundfolie); #endif for(int sp=1; sp <=n;sp++) matrix[foundfolie][sp] = false; changed = true; rescnt++; res[foundfolie]=i; } if (res[i]!=0) continue; // auf Folie i nur eine Zahl int foundnr=0, cspalte=0; for (int spalte=1;spalte<=n;spalte++) { if (matrix[i][spalte]) { cspalte++; foundnr = spalte; #ifdef TESTOUT printf("on slide %d found %d (%d)\n", i, spalte, cspalte); #endif } } if (cspalte==1) { for (int ze=1; ze<=n;ze++) { matrix[ze][foundnr]=false; } changed = true; rescnt++; res[i]=foundnr; } } } //Output cout <<"Heap "<0) printf("(%c,%d) ",int2char(i),res[i]); cout << endl; } cout << endl; } return 1; }