Advertisement
Guest User

Untitled

a guest
Oct 2nd, 2014
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <set>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. struct event{
  10.     int x, yD, yG, tip, p;
  11.     event(){}
  12.  
  13.     event( int _x, int _yD, int _yG, int _tip, int _p ){
  14.         x = _x; yD = _yD; yG = _yG; tip = _tip; p = _p;
  15.     }
  16. };
  17.  
  18. const int maxn = 100005;
  19.  
  20. int N;
  21.  
  22. vector< event > V;
  23. set< pair< int, int > > donje, gornje;
  24. set< pair< int, int > > :: iterator itD;
  25. set< pair< int, int > > :: iterator itG;
  26.  
  27. int parent[ maxn ];
  28.  
  29. int find( int x ){
  30.     if( parent[ x ] == x ) return x;
  31. return parent[ x ] = find( parent[ x ] );
  32. }
  33.  
  34. void spoji( int a, int b ){
  35.     parent[ find( a ) ] = find( b );
  36. return;
  37. }
  38.  
  39. bool cmp( event A, event B ){
  40.     if( A.x == B.x ) return A.tip < B.tip;
  41. return A.x < B.x;
  42. }
  43.  
  44. void rijesi(){
  45.     for( int i = 0; i < N; i ++ ) parent[ i ] = i;
  46.  
  47.     for( int i = 0; i < V.size(); i ++ ){
  48.         if( V[ i ].tip == 1 ){
  49.             itD = donje.lower_bound( make_pair( V[ i ].yG, V[ i ].p ) );
  50.             itG = gornje.lower_bound( make_pair( V[ i ].yD, V[ i ].p ) );
  51.  
  52.  
  53.             if( itD != donje.end() && itD -> first == V[ i ].yG ) spoji( itD -> second, V[ i ].p );
  54.             if( itG != gornje.end() && itG -> first == V[ i ].yD ) spoji( itG -> second, V[ i ].p );
  55.  
  56.             gornje.insert( make_pair( V[ i ].yG, V[ i ].p ) );
  57.             donje.insert( make_pair( V[ i ].yD, V[ i ].p ) );
  58.         }
  59.         else{
  60.             gornje.erase( gornje.find( make_pair( V[ i ].yG, V[ i ].p ) ) );
  61.             donje.erase( donje.find( make_pair( V[ i ].yD, V[ i ].p ) ) );
  62.         }
  63.     }
  64.  
  65.  
  66. return;
  67. }
  68.  
  69. void ispisi(){
  70.     int sol = 0;
  71.     for( int i = 0; i < N; i ++ ) if( parent[ i ] == i ) sol ++;
  72.  
  73.     printf( "%d\n", sol );
  74.  
  75. return;
  76. }
  77.  
  78. void ucitaj(){
  79.     scanf( "%d", &N );
  80.     for( int i = 0; i < N; i ++ ){
  81.         int a, b, c, d;
  82.         scanf( "%d%d%d%d", &a, &b, &c, &d );
  83.  
  84.         V.push_back( event( a, b, d, 1, i ) );
  85.         V.push_back( event( c, b, d, -1, i ) );
  86.     }
  87.  
  88.     sort( V.begin(), V.end(), cmp );
  89.  
  90.     for( int i = 0; i < V.size(); i ++ ){
  91.         printf( "%d %d %d          %d \n", V[ i ].x, V[ i ].yD, V[ i ].yG, V[ i ].tip, V[ i ].p );
  92.     }
  93.  
  94. return;
  95. }
  96.  
  97. int main( void ){
  98.     ucitaj();
  99.     rijesi();
  100.     ispisi();
  101.  
  102. return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement