Cod sursa(job #26461)

Utilizator MariusMarius Stroe Marius Data 5 martie 2007 17:13:10
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const char iname[] = "pachete.in";
const char oname[] = "pachete.out";

#define MAX_N 50000

struct entry {
	int x;
	int y;
} ;

entry P[MAX_N], X[MAX_N];

int x, y;

int n;

int V[MAX_N];


void read_in(void) {
	freopen(iname, "r", stdin);
	int i;
	scanf("%d", & n);
	scanf("%d %d", & x, & y);
	for (i = 0; i < n; ++ i) {
		scanf("%d %d", & P[i].x, & P[i].y);
		P[i].x -= x;
		P[i].y -= y;
	}
}

int mycmp(entry z, entry w) {
	if (z.x != w.x) {
		if ((z.x >= 0 && z.y > 0) || (z.x > 0 && z.y <= 0))
			return z.x < w.x;
		return z.x > w.x;
	} else {
		if ((z.x >= 0 && z.y > 0) || (z.x < 0 && z.y >= 0))
			return z.y < w.y;
		return z.y > w.y;
	}
}

int search(int V[], int n, int key) {
	int k;
	int stp;
	for (stp = 1; stp <= n; stp <<= 1) ;
	for (k = 0;   stp;      stp >>= 1) {
		if (k + stp <= n && key < V[k + stp])
			k = stp + k;
	}
	return k;
}

int num(const int cadran) {
	int cnt = 0;
	int i;
	if (cadran == 1) {
		for (i = 0; i < n; ++ i)
			if (P[i].x >= 0 && P[i].y >  0)	X[cnt ++] = P[i];
	}
	if (cadran == 2) {
		for (i = 0; i < n; ++ i)
			if (P[i].x <  0 && P[i].y >= 0) X[cnt ++] = P[i];
	}
	if (cadran == 3) {
		for (i = 0; i < n; ++ i)
			if (P[i].x <= 0 && P[i].y <  0) X[cnt ++] = P[i];
	}
	if (cadran == 4) {
		for (i = 0; i < n; ++ i)
			if (P[i].x >  0 && P[i].y <= 0) X[cnt ++] = P[i];
	}
	sort(X, X + cnt, mycmp);
	for (i = 0; i < cnt; ++ i) {
		if (X[i].x < 0) 
			X[i].x = - X[i].x;
		if (X[i].y < 0)
			X[i].y = - X[i].y;
	}
	int size = 0;
	for (i = 0; i < cnt; ++ i) {
		int k = search(V, size, X[i].y);
		V[k + 1] = X[i].y;
		if (k == size)
			size ++;
	}
	return size;
}

int main(void) {
	read_in();
	int Res = 0;
	for (int i = 1; i <= 4; ++ i)
		Res += num(i);
	freopen(oname, "w", stdout);
	printf("%d\n", Res);
	return 0;
}