Cod sursa(job #4931)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 8 ianuarie 2007 21:50:54
Problema Dreptunghiuri Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <cstring>

const int NMAX = 401;

int N, M;
int SQ[NMAX * NMAX];
long long cnt;

void read() {
	FILE *fin = fopen("dreptunghiuri.in", "rt");

	fscanf(fin, " %d %d", &N, &M);

	if (M > N) {
		int aux = N;
		N = M; M = aux;
	}

	fclose(fin);
}

void prepare() {
	int i;
	
	memset(SQ, 0xff, sizeof(SQ));

	for (i = 0; i < NMAX; ++i)
		SQ[i * i] = i;
}

void count() {
	int i, j, k, p, t = 0;
	int c, d, r;
	bool ok;

	for (i = 1; i < N; ++i)
		for (j = 1; j <= i; ++j) {
			for (k = p = 0; k < i; ++k) {
				ok = true;
				
				c = k * (i - k);
				d = j * j - 4 * c;

				r = -1;
				if (d < 0) 
					ok = false;
				else
					r = SQ[d];

				if (r < 0) ok = false;

				if ( r >= 0 && ((j ^ r) & 1) == 0 && r <= j )
					t = r == j || r == 0 ? 1 : 2;
				else
					ok = false;

				if (ok) p += t;				
			}

			if (i < M && i != j) p <<= 1;
			cnt += p * (N - i) * (M - j);
//			printf("%d %d %d %lld\n", i, j, p, cnt);
		}

}

void write() {
	FILE *fout = fopen("dreptunghiuri.out", "wt");

	fprintf(fout, "%lld\n", cnt);

	fclose(fout);
}

int main() {

	read();

	prepare();

	count();

	write();

	return 0;
}