| UVA - 11134 |
We would like to place n rooks, 1 ≤ n ≤ 5000, on a n × n board subject to the following restrictions
The i-th rook can only be placed within the rectan- gle given by its left-upper corner (xli,yli) and its right- lower corner (xri,yri), where 1 ≤ i ≤ n, 1 ≤ xli ≤ xri ≤n,1≤yli ≤yri ≤n.
-
No two rooks can attack each other, that is no two rooks can occupy the same column or the same row.
Input
The input consists of several test cases. The first line of each
of them contains one integer number, n, the side of the board. n lines follow giving the rectangles
where the rooks can be placed as described above. The i-th line among them gives xli, yli, xri, and
yri. The input file is terminated with the integer ‘0’ on a line by itself.Output
Your task is to find such a placing of rooks that the above conditions are satisfied and then output n
lines each giving the position of a rook in order in which their rectangles appeared in the input. If there
are multiple solutions, any one will do. Output ‘IMPOSSIBLE’ if there is no such placing of the rooks.Sample Input
8
1122
5788
2255
2255
6386
6385
6388
3678
8
1122
5788
2255
2255
6386
6385
6388
3678
0Sample Output
11
58
24
42
73
85
66
37
11
58
24
42
73
85
66
37
白书
在n*n的棋盘上面放n个车,能否使他们互相不攻击(即不能在同一行一列),并且第i个车必须落在第i的矩形范围(xl,yl, xr,yr)之内
//
// main.cpp
// uva11134
//
// Created by Candy on 10/17/16.
// Copyright © 2016 Candy. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=5e3+,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n;
int x[N],y[N];
struct data{
int id;
int l1,r1,l2,r2;
}a[N];
//bool cmp1(data &x,data &y){
// if(x.l1==y.l1) return x.r1<y.r1;
// else return x.l1<y.l1;
//}
//bool cmp2(data &x,data &y){
// if(x.l2==y.l2) return x.r2<y.r2;
// return x.l2<y.l2;
//}
//bool solve(){
// sort(a+1,a+1+n,cmp1);
// int p=1;
// for(int i=1;i<=n;i++){
// //printf("hi%d %d %d %d\n",i,a[i].l1,a[i].r1,a[i].id);
// if(a[p].l1<=i&&i<=a[p].r1) x[a[p++].id]=i;
// else if(a[p].r1<i||a[p].l1>i) return 0;
// }
//
// sort(a+1,a+1+n,cmp2);
// p=1;
// for(int i=1;i<=n;i++){
// //printf("ih%d %d %d %d\n",i,a[i].l2,a[i].r2,a[i].id);
// if(a[p].l2<=i&&i<=a[p].r2) y[a[p++].id]=i;
// else if(a[p].r2<i||a[p].l2>i) return 0;
// }
// return 1;
//}
bool sol(){
memset(x,,sizeof(x));
memset(y,,sizeof(y));
for(int i=;i<=n;i++){
int rook=,mnr=INF;
for(int j=;j<=n;j++)
if(!x[j]&&a[j].l1<=i&&a[j].r1<mnr) rook=j,mnr=a[j].r1;
//printf("rook1 %d\n",rook);
if(rook==||a[rook].r1<i) return false;
x[rook]=i;
}
for(int i=;i<=n;i++){
int rook=,mnr=INF;
for(int j=;j<=n;j++)
if(!y[j]&&a[j].l2<=i&&a[j].r2<mnr) rook=j,mnr=a[j].r2;
//printf("rook2 %d\n",rook);
if(rook==||a[rook].r2<i) return false;
y[rook]=i;
}
return ;
}
int main(int argc, const char * argv[]) {
while((n=read())){
for(int i=;i<=n;i++){
a[i].id=i;
a[i].l1=read();a[i].l2=read();a[i].r1=read();a[i].r2=read();
}
if(sol()){
for(int i=;i<=n;i++) printf("%d %d\n",x[i],y[i]);
}else printf("IMPOSSIBLE\n");
} return ;
}