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