注意到行列互不影响,所以将行列分开考虑
问题转化为:给定 (n) 条线段,填入 (n) 个格子,使得每个线段都被填入一个格子,且同一个格子只能填入一个线段
贪心,一个一个格子来看,所以将所有线段按左端点排序,该格子可以填入左端点在该格子左边的所有线段,为了保证最优,
再将这些线段按右端点排序,将格子依次填入线段即可
注意不合法的情况:
- 取出线段后,线段的右端点在该格子之前,此时该线段无法填入格子,不合法
- 没有剩余线段的左端点在该格子的左边,此时该格子无法填入线段,不合法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5010;
int n;
struct Seg{
int id;
int l, r;
bool operator < (const Seg &x) const{
return r > x.r;
}
}a[maxn], b[maxn];
bool cmp(Seg p, Seg q){
return p.l < q.l;
}
int x[maxn], y[maxn];
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
int main(){
while(scanf("%d", &n) == 1 && n){
int xl, yl, xr, yr;
for(int i = 1 ; i <= n ; ++i){
scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
a[i].l = xl, a[i].r = xr, a[i].id = i;
b[i].l = yl, b[i].r = yr, b[i].id = i;
}
sort(a + 1, a + 1 + n, cmp);
sort(b + 1, b + 1 + n, cmp);
priority_queue<Seg> q;
while(!q.empty()) q.pop();
int pos = 1;
int flag = true;
for(int i = 1 ; i <= n ; ++i){
while(a[pos].l <= i && pos <= n) {
q.push(a[pos++]);
}
if(q.empty()) flag = false;
if(!q.empty()){
Seg u = q.top(); q.pop();
if(u.r < i) {
flag = false;
break;
}
x[u.id] = i;
}
}
if(!flag){
printf("IMPOSSIBLE
");
continue;
}
while(!q.empty()) q.pop();
pos = 1;
flag = true;
for(int i = 1 ; i <= n ; ++i){
while(b[pos].l <= i && pos <= n) {
q.push(b[pos++]);
}
if(q.empty()) flag = false;
if(!q.empty()){
Seg u = q.top(); q.pop();
if(u.r < i) {
flag = false;
break;
}
y[u.id] = i;
}
}
if(!flag){
printf("IMPOSSIBLE
");
continue;
}
for(int i = 1 ; i <= n ; ++i){
printf("%d %d
", x[i], y[i]);
}
}
return 0;
}