Cod sursa(job #266962)

Utilizator scvalexAlexandru Scvortov scvalex Data 26 februarie 2009 14:46:38
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int Dir[4][2] = {
	{1, 1},
	{1, -1},
	{-1, 1},
	{-1, -1}
};

typedef struct {
	int x, y;
} Point;

int N, X, Y;
Point P[50000];
int M;
Point Q[50000];
int ND;
int D[50000];

void filter(int ox, int oy) {
	int i;
	M = 0;
	for (i = 0; i < N; ++i)
		if (((P[i].x - X) * ox >= 0) && ((P[i].y - Y) * oy >= 0)) {
			Q[M++] = P[i];
		}
}

bool plt0(const Point &a, const Point &b) {
	if (a.x == b.x)
		return (a.y < b.y);
	return (a.x < b.x);
}

bool plt1(const Point &a, const Point &b) {
	if (a.x == b.x)
		return (a.y > b.y);
	return (a.x < b.x);
}

bool plt2(const Point &a, const Point &b) {
	if (a.x == b.x)
		return (a.y > b.y);
	return (a.x > b.x);
}

bool plt3(const Point &a, const Point &b) {
	if (a.x == b.x)
		return (a.y > b.y);
	return (a.x > b.x);
}

int main(int argc, char *argv[]) {
	int i, j, k, m, t;

	FILE *fi = fopen("pachete.in", "r");
	fscanf(fi, "%d", &N);
	fscanf(fi, "%d %d", &X, &Y);
	for (i = 0; i < N; ++i)
		fscanf(fi, "%d %d", &P[i].x, &P[i].y);
	fclose(fi);

	/*for (i = 0; i < N; ++i)
		printf("(%d, %d) ", P[i].x, P[i].y);
	printf("\n");*/

	t = 0;
	for (k = 0; k < 4; ++k) {
		filter(Dir[k][0], Dir[k][1]);
		switch (k) {
			case 0: 
				sort(Q, Q+M, plt0);
				break;
			case 1:
				sort(Q, Q+M, plt1);
				break;
			case 2:
				sort(Q, Q+M, plt2);
				break;
			case 3:
				sort(Q, Q+M, plt3);
				break;
		};
		/*if (Dir[k][0] < 0)
			reverse(Q, Q+M);*/

		/*printf("(%d, %d): ", Dir[k][0], Dir[k][1]);
		for (i = 0; i < M; ++i)
			printf("(%d, %d) ", Q[i].x, Q[i].y);
		printf("\n");*/

		ND = 0;
		for (i = 0; i < M; ++i) {
			m = -1;
			for (j = ND-1; j >= 0; --j)
				if ((Q[i].y - Q[D[j]].y) * Dir[k][1] >= 0) {
					m = j;
					break;
				}
			if (m != -1) {
				D[m] = i;
				//printf("Adaug (%d, %d) la sirul %d.\n", Q[i].x, Q[i].y, m);
			} else {
				D[ND++] = i;
				//printf("Construiesc un nou sir (%d) pentru (%d, %d).\n", ND-1, Q[i].x, Q[i].y);
			}
		}
		t += ND;

		//printf("%d\n", ND);
	}

	//printf("%d\n", t);
	
	FILE *fo = fopen("pachete.out", "w");
	fprintf(fo, "%d\n", t);
	fclose(fo);

	return 0;
}