Advertisement
Guest User

Untitled

a guest
Jun 28th, 2013
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<queue>
  4. #include<cstdlib>
  5. #define MAX_N 3010
  6. using namespace std;
  7.  
  8. int n;
  9. int ansx[MAX_N], ansy[MAX_N];
  10.  
  11. struct rock_tag {
  12.     int x1,x2,y1,y2;
  13. } rock[MAX_N];
  14.  
  15. struct compute_tag {
  16.     int x,y;
  17.     int id;
  18.    
  19.     bool operator < ( const compute_tag &T ) const {
  20.         return T.y < y;
  21.     }
  22.    
  23. } a[MAX_N];
  24.  
  25. priority_queue< compute_tag > Q;
  26.  
  27. bool cmp( compute_tag p , compute_tag q )
  28. {
  29.     return p.x < q.x;
  30. }
  31.  
  32. void endprogram()
  33. {
  34.     printf("NIE\n");
  35.     exit(0);
  36. }
  37.  
  38. void solve(int ans[])
  39. {
  40.     sort( a+1 , a+1+n , cmp );
  41.     int now = 1;
  42.     for(int c=1;c<=n;c++)
  43.     {
  44.         while( a[now].x <= c and now <= n )
  45.         {
  46.             Q.push( a[now] );
  47.             now ++;
  48.         }
  49.         if( Q.empty() ) endprogram();
  50.         compute_tag z = Q.top();
  51.         Q.pop();
  52.         if( z.y < c ) endprogram();
  53.         ans[ z.id ] = c;
  54.     }
  55. }
  56.  
  57. int main()
  58. {
  59.     scanf("%d",&n);
  60.     for(int c=1;c<=n;c++) scanf("%d%d%d%d",&rock[c].x1,&rock[c].y1,&rock[c].x2,&rock[c].y2);
  61.     for(int c=1;c<=n;c++) a[c].x = rock[c].x1, a[c].y = rock[c].x2, a[c].id = c;
  62.     solve( ansx );
  63.     for(int c=1;c<=n;c++) a[c].x = rock[c].y1, a[c].y = rock[c].y2, a[c].id = c;
  64.     solve( ansy );
  65.     for(int c=1;c<=n;c++) printf("%d %d\n",ansx[c],ansy[c]);
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement