Cod sursa(job #4917)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 8 ianuarie 2007 21:02:42
Problema Dreptunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 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);

	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;
	int c, d, r;
	bool ok;

	for (i = 1; i < N; ++i)
		for (j = 1; j < M; ++j) {
			for (k = p = 1; 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 ((j + r) & 1) ok = false;

				if (r >= j) ok = false;

				if (ok) ++p;				
			}

			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", cnt);

	fclose(fout);
}

int main() {

	read();

	prepare();

	count();

	write();

	return 0;
}