比赛 20100422 评测结果 AAA
题目名称 烦人的幻灯片 最终得分 100
用户昵称 lc 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-04-22 11:02:28
显示代码纯文本
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn = 30;
int N,M,Ans,S0=0,T0=0;
int matchx[maxn],matchy[maxn];
bool G[maxn][maxn],vis[maxn];
struct coortype
{
	int x,y;
}point[maxn];
struct slidetype
{
	int x1,y1,x2,y2;
}slide[maxn];


void prep()
{
	scanf("%d",&N);
	for (int i=1; i<=N; i++)
	{
		scanf("%d%d%d%d",&slide[i].x1,&slide[i].x2,&slide[i].y1,&slide[i].y2);
	}
	for (int i=1; i<=N; i++)
	{
		scanf("%d%d",&point[i].x,&point[i].y);
	}
}

bool Can(int X,int Y)
{
	if (point[Y].x >=slide[X].x1 && point[Y].x <=slide[X].x2 && 
		point[Y].y >=slide[X].y1 && point[Y].y <=slide[X].y2)
		return true;
	return false;
}

void Make_Graph()
{
	for (int i=1; i<=N; i++)
		for (int j=1; j<=N; j++)
			if (Can(i,j)) G[i][j] = true;
}

bool Findpath(int v)
{
	if (vis[v]) return false;
	vis[v] = true;
	
	for (int i=1; i<=N; i++)
	{
		if (!G[v][i]) continue;
		if (v==S0 && i==T0) continue;
		if (matchy[i]==0 || Findpath(matchy[i]))
		{
			matchy[i] =v; matchx[v] = i;
			return true;
		}
	}
	
	return false;
}

void work()
{
	Make_Graph();
	for (int i=1; i<=N; i++)
	{
		memset(vis,0,sizeof(bool)*(N+1));
		if (Findpath(i)) Ans++;
	}
	if (Ans <N)
	{
		printf("None\n"); return;
	}
	
	for (int i=1; i<=N; i++)
	{
		memset(vis,0,sizeof(bool)*(N+1));
		S0 = i; T0 = matchx[i];
		matchy[T0] = 0;
		if (Findpath(i))
		{
			printf("None\n"); return;
		}
		matchy[T0] = S0;
	}
	
	for (int i=1; i<=N; i++)
	{
		printf("%c %d\n",'A'+i-1,matchx[i]);
	}
}

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