Cod sursa(job #7484)

Utilizator gcosminGheorghe Cosmin gcosmin Data 21 ianuarie 2007 16:10:38
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

#define NMAX 50010

int N;

int nr[4];
pair <int, int> nod[4][NMAX];

set <int> H;

int make(int q)
{
	int rez = 0;
	
	sort(nod[q] + 1, nod[q] + nr[q] + 1);

//	for (int i = 1; i <= nr[q]; i++) printf("%d %d | ", nod[q][i].first, nod[q][i].second);
//	printf("\n");

	H.clear();

	set <int> :: iterator it;

	for (int i = 1; i <= nr[q]; i++) {
		it = H.lower_bound(nod[q][i].second);

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

		H.insert(nod[q][i].second);
	}	

return rez;
}

int main()
{
	int i, x, y, xb, yb;
	
	freopen("pachete.in", "r", stdin);
	freopen("pachete.out", "w", stdout);

	scanf("%d", &N);

	scanf("%d %d", &xb, &yb);

	for (i = 1; i <= N; i++) {
		scanf("%d %d", &x, &y);

		x -= xb;
		y -= yb;

		if (x > 0 && y > 0) nr[0]++, nod[0][nr[0]].first = x, nod[0][nr[0]].second = y;
		if (x < 0 && y > 0) nr[1]++, nod[1][nr[1]].first = -x, nod[1][nr[1]].second = y;
		if (x < 0 && y < 0) nr[2]++, nod[2][nr[2]].first = -x, nod[2][nr[2]].second = -y;
		if (x > 0 && y < 0) nr[3]++, nod[3][nr[3]].first = x, nod[3][nr[3]].second = -y;
	}

	int rez = 0;

	rez += make(0);
	rez += make(1);
	rez += make(2);
	rez += make(3);

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

fclose(stdin);
fclose(stdout);
return 0;
}