Cod sursa(job #843150)

Utilizator stoicatheoFlirk Navok stoicatheo Data 27 decembrie 2012 15:11:15
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 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;
}