1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=5000+50; 5 int ansx[maxn]; 6 int ansy[maxn]; 7 int visx[maxn]; 8 int visy[maxn]; 9 struct nodex 10 { 11 int l,r,num; 12 bool operator < (const nodex& rhs) 13 { 14 if(r!=rhs.r) 15 { 16 return r<rhs.r; 17 } 18 else return l<rhs.l; 19 } 20 }x[maxn]; 21 struct nodey 22 { 23 int l,r,num; 24 bool operator < (const nodey& rhs) 25 { 26 if(r!=rhs.r) 27 { 28 return r<rhs.r; 29 } 30 else return l<rhs.l; 31 } 32 }y[maxn]; 33 int main() 34 { 35 int n; 36 while(scanf("%d",&n)&&n) 37 { 38 int ansx[maxn]={0}; 39 int ansy[maxn]={0}; 40 int visx[maxn]={0}; 41 int visy[maxn]={0}; 42 for(int i=1;i<=n;i++) 43 { 44 int xl,yl,xr,yr; 45 scanf("%d%d%d%d",&xl,&yl,&xr,&yr); 46 x[i].num=i; 47 x[i].l=xl; 48 x[i].r=xr; 49 y[i].num=i; 50 y[i].l=yl; 51 y[i].r=yr; 52 } 53 sort(x+1,x+n+1); 54 sort(y+1,y+n+1); 55 int flag=1; 56 for(int i=1;i<=n;i++) 57 { 58 while(visx[x[i].l]&&x[i].l<=x[i].r) 59 { 60 x[i].l++; 61 } 62 if(x[i].l>x[i].r) 63 { 64 flag=0; 65 break; 66 } 67 visx[x[i].l]=1; 68 ansx[x[i].num]=x[i].l; 69 } 70 for(int i=1;i<=n;i++) 71 { 72 while(visy[y[i].l]&&y[i].l<=y[i].r) 73 { 74 y[i].l++; 75 } 76 if(y[i].l>y[i].r) 77 { 78 flag=0; 79 break; 80 } 81 visy[y[i].l]=1; 82 ansy[y[i].num]=y[i].l; 83 } 84 if(!flag) printf("IMPOSSIBLE "); 85 else 86 { 87 for(int i=1;i<=n;i++) 88 { 89 printf("%d %d ",ansx[i],ansy[i]); 90 } 91 } 92 } 93 return 0; 94 95 }
简单的贪心，回归到最基本的模型，每个点取可取端点的最左边即可。