记录编号	16195	评测结果	AAA
题目名称	烦人的幻灯片	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2010-04-22 11:50:40	内存使用	0.34 MiB

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
const int maxn=100;
const int maxm=maxn*maxn;


struct edge
{
	int t;
	edge *next;
}E[maxm],*V[maxn],*FV[maxn];

int xmin[maxn],xmax[maxn],ymin[maxn],ymax[maxn],eh;

inline void addedgeV(int a,int b)
{
	E[++eh].next=V[a];  V[a]=E+eh;  V[a]->t = b;
}

inline void addedgeFV(int a,int b)
{
	E[++eh].next=FV[a];  FV[a]=E+eh;  FV[a]->t = b;
}

int n;

void init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	scanf("%d%d%d%d",&xmin[i],&xmax[i],&ymin[i],&ymax[i]);
	int x,y;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		for (int j=n;j>=1;j--)
		if (xmin[j]<=x && x<=xmax[j] && ymin[j]<=y && y<=ymax[j])
		addedgeV(i,j+n);
		for (int j=1;j<=n;j++)
		if (xmin[j]<=x && x<=xmax[j] && ymin[j]<=y && y<=ymax[j])
		addedgeFV(i,j+n);
	}
}

int to[maxn],fto[maxn];
bool y[maxn];

bool crosspath(int u)
{
	for (edge *e=V[u];e;e=e->next)
	{
		int v=e->t;
		if (!y[v])
		{
			y[v]=true;
			if ( to[v]==0 || crosspath(to[v]) )
			{
				to[v]=u;
				return true;
			}
		}
	}
	return false;
}

int hungry()
{
	int match=0;
	for (int i=1;i<=n;i++)
	{
		memset(y,0,sizeof(y));
		if (crosspath(i)) match++;
	}
	return match;
}


bool fcrosspath(int u)
{
	for (edge *e=FV[u];e;e=e->next)
	{
		int v=e->t;
		if (!y[v])
		{
			y[v]=true;
			if ( fto[v]==0 || fcrosspath(fto[v]) )
			{
				fto[v]=u;
				return true;
			}
		}
	}
	return false;
}

int fhungry()
{
	int match=0;
	for (int i=1;i<=n;i++)
	{
		memset(y,0,sizeof(y));
		if (fcrosspath(i)) match++;
	}
	return match;
}

void solve()
{
	int match=hungry();
	if (match!=n) printf("None\n");
	else
	{
		fhungry();
		for (int i=1;i<=n;i++)
		if (to[i+n]!=fto[i+n])
		{
			printf("None\n");
			return;
		}
		for (int i=1;i<=n;i++)
		printf("%c %d\n",i+64,to[i+n]);
	}
}

int main()
{
	freopen("slides.in","r",stdin);
	freopen("slides.out","w",stdout);
	init();
	solve();
	return 0;
}