题意：在一个n*n的棋盘上放n个车，让它们不互相攻击，并且第i辆车在给定的小矩形内。
析：说实话，一看这个题真是没思路，后来看了分析，原来这个列和行是没有任何关系的，我们可以分开看，
把它变成两个一维问题，也就是说，我们可以把行看成是1-n，然后把x1-x2看成小区间，这样的话，
是不是就感觉简单的了，还有好几坑，被坑的惨惨的。
首先对行排序，按照每个右端点排，然后扫一遍，去找左端点，找到就立马选上（贪心），并且是一定满足的，
如果找不到，就退出，说明没有解。同理列也是这样。
后来看了Rujia Liu的代码，那叫一个精简啊，连结构体都没用，真是大神啊。
我的代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std;
const int maxn = 5000 + 10;
struct node{
int x1, x2, y1, y2;
int x, y, id;
bool usedx, usedy;
};
node a[maxn]; bool cmp1(const node &p, const node &q){ return p.x2 < q.x2; } bool cmp2(const node &p, const node &q){ return p.y2 < q.y2; } bool cmp3(const node &p, const node &q){ return p.id < q.id; } int main(){
int n;
while(scanf("%d", &n) && n){
for(int i = 0; i < n; ++i){
scanf("%d %d %d %d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
a[i].usedx = a[i].usedy = false;
a[i].id = i;
} sort(a, a+n, cmp1);
bool ok;
for(int i = 0; i < n; ++i){
ok = false;
for(int j = 0; j < n; ++j){
if(!a[j].usedx && a[j].x1 <= i+1){
if(a[j].x2 <= i) break;
a[j].x = i+1;
a[j].usedx = true;
ok = true;
break;
}
}
if(!ok) break;
}
if(!ok){ printf("IMPOSSIBLE\n"); continue; } // puts("++++");
sort(a, a+n, cmp2);
for(int i = 0; i < n; ++i){
ok = false;
for(int j = 0; j < n; ++j){
if(!a[j].usedy && a[j].y1 <= i+1){
if(a[j].y2 <= i) break;
a[j].y = i+1;
a[j].usedy = true;
ok = true;
break;
}
}
if(!ok) break;
}
if(!ok){ printf("IMPOSSIBLE\n"); continue; } sort(a, a+n, cmp3);
for(int i = 0; i < n; ++i)
printf("%d %d\n", a[i].x, a[i].y);
}
return 0;
}
下面是Rujai Liu的代码真是膜拜啊：
#include<cstdio>
#include<cstring>
#include <algorithm>
using namespace std; bool solve(int *a, int *b, int *c, int n) {
fill(c, c+n, -1);
for(int col = 1; col <= n; col++) {
int rook = -1, minb = n+1;
for(int i = 0; i < n; i++)
if(c[i] < 0 && b[i] < minb && col >= a[i]) { rook = i; minb = b[i]; }
if(rook < 0 || col > minb) return false;
c[rook] = col;
}
return true;
} const int maxn = 5000 + 5;
int n, x1[maxn], yy1[maxn], x2[maxn], y2[maxn], x[maxn], y[maxn]; int main() {
while(scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++)
scanf("%d%d%d%d", &x1[i], &yy1[i], &x2[i], &y2[i]);
if(solve(x1, x2, x, n) && solve(yy1, y2, y, n))
for (int i = 0; i < n; i++) printf("%d %d\n", x[i], y[i]);
else
printf("IMPOSSIBLE\n");
}
return 0;
}