Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <iostream>
- #include <set>
- #include <vector>
- using namespace std;
- struct event{
- int x, yD, yG, tip, p;
- event(){}
- event( int _x, int _yD, int _yG, int _tip, int _p ){
- x = _x; yD = _yD; yG = _yG; tip = _tip; p = _p;
- }
- };
- const int maxn = 100005;
- int N;
- vector< event > V;
- set< pair< int, int > > donje, gornje;
- set< pair< int, int > > :: iterator itD;
- set< pair< int, int > > :: iterator itG;
- int parent[ maxn ];
- int find( int x ){
- if( parent[ x ] == x ) return x;
- return parent[ x ] = find( parent[ x ] );
- }
- void spoji( int a, int b ){
- parent[ find( a ) ] = find( b );
- return;
- }
- bool cmp( event A, event B ){
- if( A.x == B.x ) return A.tip < B.tip;
- return A.x < B.x;
- }
- void rijesi(){
- for( int i = 0; i < N; i ++ ) parent[ i ] = i;
- for( int i = 0; i < V.size(); i ++ ){
- if( V[ i ].tip == 1 ){
- itD = donje.lower_bound( make_pair( V[ i ].yG, V[ i ].p ) );
- itG = gornje.lower_bound( make_pair( V[ i ].yD, V[ i ].p ) );
- if( itD != donje.end() && itD -> first == V[ i ].yG ) spoji( itD -> second, V[ i ].p );
- if( itG != gornje.end() && itG -> first == V[ i ].yD ) spoji( itG -> second, V[ i ].p );
- gornje.insert( make_pair( V[ i ].yG, V[ i ].p ) );
- donje.insert( make_pair( V[ i ].yD, V[ i ].p ) );
- }
- else{
- gornje.erase( gornje.find( make_pair( V[ i ].yG, V[ i ].p ) ) );
- donje.erase( donje.find( make_pair( V[ i ].yD, V[ i ].p ) ) );
- }
- }
- return;
- }
- void ispisi(){
- int sol = 0;
- for( int i = 0; i < N; i ++ ) if( parent[ i ] == i ) sol ++;
- printf( "%d\n", sol );
- return;
- }
- void ucitaj(){
- scanf( "%d", &N );
- for( int i = 0; i < N; i ++ ){
- int a, b, c, d;
- scanf( "%d%d%d%d", &a, &b, &c, &d );
- V.push_back( event( a, b, d, 1, i ) );
- V.push_back( event( c, b, d, -1, i ) );
- }
- sort( V.begin(), V.end(), cmp );
- for( int i = 0; i < V.size(); i ++ ){
- printf( "%d %d %d %d \n", V[ i ].x, V[ i ].yD, V[ i ].yG, V[ i ].tip, V[ i ].p );
- }
- return;
- }
- int main( void ){
- ucitaj();
- rijesi();
- ispisi();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement