Cod sursa(job #24826)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 3 martie 2007 18:21:18
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <algorithm>
#include <set>

using namespace std;

const int N_MAX = 50010;

pair <int, int> pct[4][N_MAX];
set <int> H;
int nr[4];

int nrd(int c)
{
	int i;
	sort(pct[c] + 1, pct[c] + nr[c] + 1);
	int rez = 0;

	H.clear();
	set <int>::iterator it;

	for (i = 1; i <= nr[c]; i ++) {
		it = H.lower_bound(pct[c][i].second);

		if (it == H.begin()) {
			rez ++;
		} else {
			-- it;
			H.erase(it);
		}

		H.insert(pct[c][i].second);
	}

	return rez;
}

int main()
{
	freopen("pachete.in", "r", stdin);
	freopen("pachete.out", "w", stdout);

	int N, i, x, y, X, Y;
	scanf("%d\n", &N);
	scanf("%d %d\n", &X, &Y);
	
	for (i = 1; i <= N; i ++) {
		scanf("%d %d\n", &x, &y);

		x -= X, y -= Y;

		if (x > 0 && y > 0) {
			pct[0][++ nr[0]].first = x, pct[0][nr[0]].second = y;
		}
		if (x < 0 && y > 0) {
			pct[1][++ nr[1]].first = -x, pct[1][nr[1]].second = y;
		}
		if (x < 0 && y < 0) {
			pct[2][++ nr[2]].first = -x, pct[2][nr[2]].second = -y;
		}
		if (x > 0 && y < 0) {
			pct[3][++ nr[3]].first = x, pct[3][nr[3]].second = -y;
		}
	}
	
	printf("%d\n", nrd(0) + nrd(1) + nrd(2) + nrd(3));
	
	return 0;
}