Cod sursa(job #825940)

Utilizator ChallengeMurtaza Alexandru Challenge Data 29 noiembrie 2012 20:39:32
Problema Dreptunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>

using namespace std;

const char InFile[]="dreptunghiuri.in";
const char OutFile[]="dreptunghiuri.out";
const int MaxN=405;
const int MaxVal=MaxN*MaxN;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M,_sqr[MaxN],_sqrt[MaxVal],D[MaxN][MaxN];
long long sol=0;

int main()
{
	fin>>N>>M;
	fin.close();

	for(register int i=0;i<MaxVal;++i)
	{
		_sqrt[i]=-1;
	}
	for(register int i=0;i<MaxN;++i)
	{
		_sqr[i]=i*i;
		_sqrt[_sqr[i]]=i;
	}
	
	int L=N;
	if(L<M)
	{
		L=N;
	}
	for(register int W=2;W<=L;++W)
	{
		for(register int H=W;H<=L;++H)
		{
			for(register int A=0;A<=H;++A)
			{
				int b=W;
				int c=A*(H-A);
				int delta=_sqrt[_sqr[b]+(c<<2)];
				if(delta!=-1)
				{

					int x1=-b+delta;
					int x2=-b-delta;

					if(!(x1&1))
					{
						x1>>=1;
						if(0<=x1 && x2<=W)
						{
							++D[W][H];
						}
					}
					if(!(x2&1))
					{
						x2>>=1;
						if(0<=x2 && x2<=W)
						{
							++D[W][H];
						}
					}
				}
			}
		}
	}

	for(register int W=2;W<=N;++W)
	{
		for(register int H=2;H<=M;++H)
		{
			int x=W;
			int y=H;
			if(x<y)
			{
				swap(x,y);
			}
			sol+=1LL*(N-W+1)*(M-H+1)*D[x][y];
		}
	}

	fout<<sol;
	fout.close();
	return 0;
}