Cod sursa(job #6986)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 21 ianuarie 2007 11:26:26
Problema Pachete Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 0.81 kb
#include <cstdio>
#define FIN "pachete.in"
#define FOUT "pachete.out"
#define MAX 50010

struct point {
	long x, y;
} A[MAX];
long N, nr;
char T[MAX];
long M[MAX];

void load_data() {
	long i;

	freopen(FIN, "r", stdin);
	scanf("%ld", &N);
	for (i=0; i<=N; ++i)
		scanf("%ld %ld", &A[i].x, &A[i].y);
	fclose(stdin);
}

inline long abs(long x) {
	return (x<0) ? -x : x;
}

inline long manh(point A, point B) {

	return abs(A.x-B.x)+abs(A.y-B.y);
}

void df(long x) {
	long i, ok=1;
	for (i=1; i<=N; ++i)
		if ( !T[i] && manh(A[x], A[i]) + M[x] == M[i] ) {
			T[i] = x;
			df(i);
			ok=0;
		}
	nr += ok;
}

void write_data() {
	freopen(FOUT, "w", stdout);
	printf("%ld\n", nr);
	fclose(stdout);
}

int main() {
	long i;

	load_data();
	nr = 0;
	for (i=1; i<=N; ++i)
		M[i] = manh(A[0], A[i]);
	df(0);
	write_data();
	return 0;
}