Pagini recente » Cod sursa (job #103347) | Cod sursa (job #1298241) | Cod sursa (job #93084) | Cod sursa (job #1650066) | Cod sursa (job #7064)
Cod sursa(job #7064)
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int sx,sy;
int loc[50001][2];
int n;
vector<int> ox;
vector<int> oy;
int pozox[50001];
int pozoy[50001];
int cc,drum;
vector<int> fii[50001];
int bagat[50001];
bool cmpf( const int &a, const int &b )
{
if ( loc[a][cc] < loc[b][cc] ) return 1;
else return 0;
}
void do_stuff( int nodc )
{
bagat[ nodc ] = 1;
int pox, poy;
int i;
vector<int>::iterator itox;
vector<int>::iterator itoy;
if ( loc[ nodc ][ 0 ] > sx ) pox = 1;
else pox = -1;
if ( loc[ nodc ][ 1 ] > sy ) poy = 1;
else poy = -1;
itox = ox.begin() + pozox[ nodc ];
itoy = oy.begin() + pozoy[ nodc ];
if ( pox > 0 )
{
itoy++;
for ( i = pozox[ nodc ]+1; i < ox.size(); i++ )
{
if ( poy > 0 )
{
if ( binary_search( itoy, oy.end(), ox[i] ) )
{
fii[ nodc ].push_back( ox[i] );
do_stuff( ox[i] );
}
}
else
if ( binary_search( oy.begin(), itoy, ox[i] ) )
{
fii[ nodc ].push_back( ox[i] );
do_stuff( ox[i] );
}
}
}
else
for ( i = pozox[ nodc ]-1; i >= 0 ; i-- )
{
if ( poy > 0 )
{
if ( binary_search( itoy, oy.end(), ox[i] ) )
{
fii[ nodc ].push_back( ox[i] );
do_stuff( ox[i] );
}
}
else
if ( binary_search( oy.begin(), itoy, ox[i] ) )
{
fii[ nodc ].push_back( ox[i] );
do_stuff( ox[i] );
}
}
}
int main()
{
int i;
freopen("pachete.in","r",stdin);
freopen("pachete.out","w",stdout);
scanf("%d\n", &n);
scanf("%d %d\n", &sx, &sy );
for ( i = 1; i <= n; i++ )
{
scanf("%d %d\n", &loc[i][0], &loc[i][1] );
ox.push_back(i);
oy.push_back(i);
}
cc = 0; sort( ox.begin(), ox.end(), cmpf );
cc = 1; sort( oy.begin(), oy.end(), cmpf );
for ( i = 0 ; i < n; i++ )
{
pozox[ ox[i] ] = i;
pozoy[ oy[i] ] = i;
}
for ( i = 1; i <= n; i ++ )
if ( !bagat[i] )
do_stuff( i );
for ( i = 1; i <= n; i++ )
if ( fii[i].size() == 0 ) drum++;
printf("%d\n", drum);
fclose(stdin);
fclose(stdout);
return 0;
}