Cod sursa(job #19230)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 18 februarie 2007 22:44:42
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

#define MAXN 50005

int N;

vector< pair<int, int> > x[4];
set< pair<int, int> > Min;
vector<int> y;

int NR = 0;

void solve( vector< pair<int, int> > &x )
{
	if (x.size() == 0)
		return;

	Min.clear();
	y.clear();

	y.push_back( x[0].second );
	Min.insert( make_pair( y[0], 0 ) );

	for (int i = 1; i < (int)x.size(); i++)
	{
		int M = (*Min.begin()).first, p = (*Min.begin()).second;
		if (x[i].second < M)
		{
			y.push_back( x[i].second );
			Min.insert( make_pair( y.back(), y.size() - 1 ) );
		}
		else
		{
			Min.erase( Min.find( make_pair( y[p], p ) ) );
			y[p] = x[i].second;
			Min.insert( make_pair( y[p], p ) );
		}
	}

	NR += y.size();
}

int main()
{
	freopen("pachete.in", "rt", stdin);
	freopen("pachete.out", "wt", stdout);
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		x[ ((a < 0) << 1) | (b < 0) ].push_back( make_pair( abs(a), abs(b)) );
	}

	for (int i = 0; i < 4; i++)
	{
		sort(x[i].begin(), x[i].end());
		x[i].resize( unique(x[i].begin(), x[i].end()) - x[i].begin() );

		solve( x[i] );
	}	

	printf("%d\n", NR);

	return 0;
}