将入度为一的区间(也就是唯一匹配的点和区间)找出来，把这个点所有出度的入度–，给这个点做标记，输出
继续执行以上操作1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
struct hu{
int x,y;
int z,w;
}a[99999];
char c[999];
int n;
int d[1999][1999];
int r[9999];
int f[99][99];
int s[99999];
int flag[999];
int main()
{
scanf("%d",&n);
for(int i=n+1;i<=2*n;i++)
{
scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].w);
c[i]='A'+i-n-1;
}
for(int i=1;i<=n;i++)
{
int x, y;
scanf("%d%d",&x,&y);
for(int j=n+1;j<=2*n;j++)
{
if(x>=a[j].x&&x<=a[j].y&&y>=a[j].z&&y<=a[j].w)
{
f[i][++f[i][0]]=j;//点的出度及对应的区间
d[j][++d[j][0]]=i;//区间入度及对应的点
r[j]++; //入度
}
}
}
for(int i=1;i<=n;i++)
{
int x=n+1;int j;
while(r[x]!=1&&x<=2*n)x++;//找入度唯一的点
r[x]=99999999;
for(j=1;j<=d[x][0];j++)
if(flag[d[x][j]]==0)
{
flag[d[x][j]]=1;
break;
}
if(x>2*n)
{
printf("None");
return 0;
}
else
s[x]=d[x][j];//记录
for(j=1;j<=f[s[x]][0];j++)
{
r[f[s[x]][j]]--;
}
}//与拓补排序相似的东西，不过是找入度唯一的。
for(int i=1+n;i<=n*2;i++) printf("%c %d\n",c[i],s[i]);//按abcd顺序输出
return 0;
}