Cod sursa(job #741863)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 27 aprilie 2012 11:28:39
Problema Dreptunghiuri Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<stdio.h>
#include<cmath>

#define maxdim 405

FILE*f=fopen("dreptunghiuri.in","r");
FILE*g=fopen("dreptunghiuri.out","w");

int n,m;
int D[maxdim][maxdim];
double rad[2*maxdim*maxdim];

inline int compute ( int L , int l ){
	int res = 1;
	
	for ( int j = 1 ; j < L ; ++j ){
		
		int delta = (l-1)*(l-1) - 4*j*(L-1) + 4*j*j;
		if ( rad[delta] != (int)rad[delta] )	continue ;
		
		delta = (int)rad[delta];
		
		double x1 = (l - 1 + delta) / 2;
		double x2 = (l - 1 - delta) / 2;
		
		if ( x1 == (int)x1 ){
			if ( x1 > 0 && x1 < l - 1 ){
				++res;
			}
		}
		if ( x1 != x2 && x2 == (int)x2 ){
			if ( x2 > 0 && x2 < l - 1 ){
				++res;
			}
		}
	}
	
	return res;
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	
	for ( int i = 1 ; i <= 320000 ; ++i ){
		rad[i] = sqrt(i);
	}
	
	long long sol = 0;
	for ( int i = 2 ; i <= n ; ++i ){
		for ( int j = i ; j <= m ; ++j ){
			int now = compute(i,j); D[i][j] = D[j][i] = now;
			sol += 1LL * now * (n-i+1) * (m-j+1);
			if ( n-j+1 > 0 && m-i+1 > 0 && i != j )
				sol += 1LL * now * (n-j+1) * (m-i+1);
		}
	}
	
	for ( int i = 2 ; i <= n ; ++i ){
		for ( int j = 2 ; j <= m ; ++j ){
			if ( !D[i][j] ){
				int now = compute(i,j);
				sol += 1LL * now * (n-i+1) * (m-j+1);
			}
		}
	}
	
	fprintf(g,"%lld\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}