Cod sursa(job #826002)

Utilizator ChallengeMurtaza Alexandru Challenge Data 29 noiembrie 2012 21:24:15
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 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;

inline int Count(int W, int H)
{
	int res=1;
	--W;--H;

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

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

			if(!(x1&1))
			{
				x1>>=1;
				if(0<x1 && x1<W)
				{
					++res;
				}
			}
			if(delta && !(x2&1))
			{
				x2>>=1;
				if(0<x2 && x2<W)
				{
					++res;
				}
			}
		}
	}
	
	return res;
}

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=M;
	}
	for(register int W=2;W<=L;++W)
	{
		for(register int H=W;H<=L;++H)
		{
			D[W][H]=D[H][W]=Count(W,H);
		}
	}

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

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