题目链接：UVA - 11134
题意描述：在一个n*n（1<=n<=5000）的棋盘上放置n个车，每个车都只能在给定的一个矩形里放置，使其n个车两两不在同一行和同一列，判断并给出解决方案。
算法分析：刚开始没有思路，后来看了别人的博客有了一点想法。我们把矩形的行和列分开解决，即n个车首先不能放置在同一行，然后判断n个车不能放置在同一列，如果都满足的话，即有正确的方法，否则就不行。那么怎样解决和判断在不在同一行并且是否可行呢，我们针对行而言，把这些行的坐标存入优先队列，首先取出最上面（行的标号较小）的，先放它，然后，再放下面的，依次往下撸就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int maxn=+; int n;
struct node
{
int l,r;
int id;
friend bool operator < (node a,node b)
{
if (a.l != b.l) return a.l > b.l ;
return a.r > b.r ;
}
}arr[maxn],arr2[maxn];
int an[maxn][]; int solve(node *a,int pos)
{
priority_queue<node> Q;
for (int i= ;i<n ;i++) Q.push(a[i]);
int weizhi=;
while (!Q.empty())
{
node temp=Q.top() ;Q.pop() ;
if (temp.r<weizhi) return ; if (temp.l<weizhi)
{
temp.l=weizhi;
Q.push(temp);
continue;
}
int m=max(temp.l,weizhi);
an[temp.id ][pos]=m;
weizhi=m+;
}
return ;
} int main()
{
while (scanf("%d",&n)!=EOF && n)
{
for (int i= ;i<n ;i++)
{
scanf("%d%d%d%d",&arr[i].l,&arr2[i].l,&arr[i].r,&arr2[i].r);
arr[i].id=arr2[i].id=i;
}
if (solve(arr,) && solve(arr2,))
{
for (int i= ;i<n ;i++)
printf("%d %d\n",an[i][],an[i][]);
}
else printf("IMPOSSIBLE \n");
}
return ;
}