比赛 |
20100422 |
评测结果 |
AWA |
题目名称 |
烦人的幻灯片 |
最终得分 |
66 |
用户昵称 |
.Xmz |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2010-04-22 09:00:52 |
显示代码纯文本
#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;
}