Cod sursa(job #7064)

Utilizator webspiderDumitru Bogdan webspider Data 21 ianuarie 2007 12:16:29
Problema Pachete Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.98 kb
#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;
}