比赛 20100422 评测结果 AWA
题目名称 烦人的幻灯片 最终得分 66
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-04-22 09:09:55
显示代码纯文本
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN=26;

int mat[MAXN],match=0;
bool g[MAXN][MAXN],used[MAXN];
int n;
int xmin[MAXN],xmax[MAXN],ymin[MAXN],ymax[MAXN];

void init()
{
	scanf("%d",&n);
	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++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		for(int j=0;j<n;j++)
			if (a>=xmin[j]&&a<=xmax[j]&&b>=ymin[j]&&b<=ymax[j])
				g[i][j]=true;
	}
	memset(mat,-1,sizeof(mat));
}

bool cross(int cur)
{
	for(int i=0;i<n;i++)
		if (g[cur][i]&&!used[i])
		{
			used[i]=true;
			if (mat[i]==-1||cross(mat[i]))
			{
				mat[i]=cur;
				return true;
			}
		}
	return false;
}

int main()
{
	freopen("slides.in","r",stdin);
	freopen("slides.out","w",stdout);
	init();
	for(int i=0;i<n;i++)
	{
		memset(used,false,sizeof(used));
		if (cross(i))
			match++;
	}
	if (match<n)printf("None");
	else
		for(int i=0;i<n;i++)
			printf("%c %d\n",'A'+i,mat[i]+1);
	return 0;
}