663

Idea:

Find the total number of matching and then check for every match(left,right) pair whether it is unique or not. To check this find total number of matching using the same algorithm just excluding a pair each time and compare the total number of founded match with the initial one. If it is not reduced than remove that pair.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>

using namespace std;
struct Slide{ int Xmin,Xmax,Ymin,Ymax;};
struct POINT{int x,y;};
vector<int> gr[105];
Slide slide[105];///////
POINT pp[105];
bool visit[105];
int lef[105],rit[105];
int N;

bool check(POINT a,Slide b)
{
	if(a.x>=b.Xmin && a.x<=b.Xmax)
	{
		if(a.y>=b.Ymin && a.y<=b.Ymax)
			return 1;
		else
			return 0;
	}
	else
		return 0;
}

bool dfs(int pos,int u,int v)
{
	for(int i=0;i<gr[pos].size();i++)
	{
		if(visit[gr[pos][i]] || (pos==u && v==gr[pos][i]))
		continue;

		visit[gr[pos][i]] = 1;

		if(rit[gr[pos][i]]==-1 || dfs(rit[gr[pos][i]],u,v))
		{
			lef[pos] = gr[pos][i];
			rit[gr[pos][i]] = pos;
			return 1;
		}
	}
	return 0;
}

int bipartite(int u,int v)
{
	for(int i=0;i<105;i++)
	{
		lef[i]=-1;rit[i]=-1;
	}
	int res =0;
	for(int i=1;i<=N;i++)
	{
		memset(visit,0,sizeof(visit));
		if(dfs(i,u,v))
		res+=1;
	}
	return res;
}
int main()
{
	int kase = 1;
	while(cin>>N)
	{
		if(!N)
		break;

		for(int i=1;i<=N;i++)
		{
			cin>>slide[i].Xmin>>slide[i].Xmax>>slide[i].Ymin>>slide[i].Ymax;
			gr[i].clear();
		}

		for(int i=1;i<=N;i++)
		{
			cin>>pp[i].x>>pp[i].y;
			for(int j=1;j<=N;j++)
			{
				if(check(pp[i],slide[j]))
				gr[j].push_back(i);
			}
		}


		int res = bipartite(-1,-1);
		int ans[105];
		for(int i=1;i<=N;i++)
			ans[i] = lef[i];

		bool space = false;
		cout<<"Heap "<<kase++<<"\n";
		for(int i=1;i<=N;i++)
		{
			if(bipartite(i,ans[i])<res)
			{
				if(space)
				cout<<" ";
				cout<<"("<<char(i+64)<<","<<ans[i]<<")";//cout<<"("<<char(ans[i]+64)<<","<<i<<")";//
				space = 1;
			}
		}
		if(!space)
		cout<<"none";
		cout<<"\n\n";
	}

	return 0;
}