比赛 |
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;
}