Cod sursa(job #330324)

Utilizator cotofanaCotofana Cristian cotofana Data 9 iulie 2009 16:19:54
Problema Dreptunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h>
#define dim 401

int n, m, sol, sqrt[dim], nrsol[dim][dim];

int main() {
	int i, tmp, h, w, a, aa, bb, cc, dd;
	freopen("dreptunghiuri.in", "r", stdin);
	freopen("dreptunghiuri.out", "w", stdout);
	
	scanf("%d %d\n", &n, &m);
	for (i=1; i*i<=400; ++i) sqrt[i*i]=i;
	
	sol=(n-1)*(m-1); //nr of rectangles with h=1 and w=1
	for (h=1; h<n; ++h)
		for (w=1; w<m; ++w)
			if (h==1 && w==1) continue;
			else if (nrsol[h][w]) sol+=nrsol[h][w];
			else if (nrsol[w][h]) sol+=nrsol[w][h];
			else {
				tmp=1; //temp nr of rect = 1(the rect itself)
				for (a=1; a<h; ++a) {
					aa=1;
					bb=-w;
					cc=a*(h-a);
					dd=bb*bb-4*aa*cc;
					if (dd<0) continue;
					if (!dd || sqrt[dd]) ++tmp;
				}
				tmp*=(n-h)*(m-w);
				nrsol[h][w]=nrsol[w][h]=tmp;
				sol+=tmp;
			}
			
	printf("%d\n", sol);
	
	return 0;
}