#include #include #include #include #include #define MAX 100 int num_vergeben[MAX]; int num_der_folie[MAX]; int x1[MAX], x2[MAX], y1[MAX], y2[MAX], fx[MAX], fy[MAX]; int num_slides; void init() { for(int i = 0; i < MAX; i++) { num_vergeben[i] = 0; num_der_folie[i] = 0; } } int testkoord(int num, int folie) { if(num_der_folie[folie] > 0) return 0; if(fx[num] <= x1[folie]) return 0; if(fx[num] >= x2[folie]) return 0; if(fy[num] <= y1[folie]) return 0; if(fy[num] >= y2[folie]) return 0; return 1; } int assign() { int m[MAX][MAX]; for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) m[i][j] = 0; for(int num = 1; num <= num_slides; num++) { for(int folie = 1; folie <= num_slides; folie++) { if(!testkoord(num, folie)) m[folie][num] = -1; } } int leftnum = num_slides; while(leftnum > 0) { int assigned = 0; for(int folie = 1; folie <= num_slides; folie++) { int count = 0; int welche_num = 0; for(int num = 1; num <= num_slides; num++) { if(m[folie][num] == 0) { count++; welche_num = num; } } if(count == 1) { for(int i = 1; i <= num_slides; i++) { m[i][welche_num] = -1; m[folie][i] = -1; } num_der_folie[folie] = welche_num; assigned = 1; leftnum--; } } // spalten for(int num = 1; num <= num_slides; num++) { int count = 0; int welche_folie = 0; for(int folie = 1; folie <= num_slides; folie++) { if(m[folie][num] == 0) { count++; welche_folie = folie; } } if(count == 1) { for(int i = 1; i <= num_slides; i++) { m[i][num] = -1; m[welche_folie][i] = -1; } num_der_folie[welche_folie] = num; assigned = 1; leftnum--; } } if(assigned == 0) { cout << "none\n\n"; return 0; } } return 1; } int read(ifstream& in) { in >> num_slides; if(num_slides == 0) return 0; for(int i = 1; i <= num_slides; i++) { in >> x1[i]; in >> x2[i]; in >> y1[i]; in >> y2[i]; } for(int i = 1; i <= num_slides; i++) { in >> fx[i]; in >> fy[i]; } return num_slides; } int main() { ifstream in("slides.in"); int set = 1; init(); while(read(in)) { cout << "Heap " << set++ << "\n"; if(assign()) { for(int i = 1; i <= num_slides; i++) { cout << "(" << (char)('A' + i - 1) << "," << num_der_folie[i] << ") "; } cout << "\n\n"; } init(); } return 0; }