Cod sursa(job #741882)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 27 aprilie 2012 12:00:28
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 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],p[maxdim];
int rad[5*maxdim*maxdim];

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

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	
	for ( int i = 1 ; i <= 800000 ; ++i ){
		double aux = sqrt(i);
		if ( aux != (int)aux ){
			rad[i] = -1;
		}
		else{
			rad[i] = (int)aux;
		}
	}
	for ( int i = 1 ; i <= 400 ; ++i ){
		p[i] = i*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;
}