#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>using namespace std;#define maxn 30bool MaxMatchDFS(bool g[][maxn], int m, int a, int y[], bool u[]){ for (int i=0; i<m; i++) if (!u[i] && g[a][i]) { int t=y[i]; u[i]=true; y[i]=a; if (t==-1 || MaxMatchDFS(g, m, t, y, u)) return true; y[i]=t; } return false;}int MaxMatch(bool g[][maxn], int n, int m) //v1[y[i]] matches v2[i]{ int y[maxn]; memset(y, 255, sizeof(y)); int c=0; for (int i=0; i<n; i++) { bool u[maxn]={0}; if (MaxMatchDFS(g, m, i, y, u)) c++; } return c;}bool init(bool g[][maxn], int &n){ int xmin[maxn], xmax[maxn], ymin[maxn], ymax[maxn]; int x[maxn], y[maxn]; scanf("%d", &n); if (n==0) return false; for (int i=0; i<n; i++) scanf("%d%d%d%d", &xmin[i], &xmax[i], &ymin[i], &ymax[i]); for (int i=0; i<n; i++) scanf("%d%d", &x[i], &y[i]); memset(g, false, sizeof(*g)*maxn); for (int i=0; i<n; i++) for (int j=0; j<n; j++) { if (xmin[i]<x[j] && xmax[i]>x[j] && ymin[i]<y[j] && ymax[i]>y[j]) g[i][j]=1; } return true;}int main(){ int cs=0; int n, unique, match; bool g[maxn][maxn]; bool found; while (init(g, n)) { found=false; printf("Heap %dn", ++cs); for (int i=0; i<n; i++) { unique=-1; //0:false 1:true -1:don't know match=-1; for (int j=0; j<n; j++) if (g[i][j]) { g[i][j]=false; if (MaxMatch(g, n, n)==n-1) { if (unique==-1){unique=1;match=j;} else {unique=0; break;} } g[i][j]=true; } if (unique==1) { if (found==false) found=true; else printf(" "); printf("(%c,%d)", i+'A', match+1); } } if (found==false) printf("nonenn"); else printf("nn"); } return 0;}
