Cod sursa(job #1173061)

Utilizator misinozzz zzz misino Data 18 aprilie 2014 15:49:57
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.26 kb
#include<fstream>

#define N 410

using namespace std;

ifstream f("dreptunghiuri.in");
ofstream g("dreptunghiuri.out");

int n,m,h,i,w,cate[N][N],rad[N*N];

long long sol;

inline int numara(int h,int w)
{
    int nr = 0;

    for(int a = 1 ; a <= w ; ++ a)
    {
        int delta = h * h - 4 * a * w + 4 * a * a;

        if(delta < 0)
            continue;

        if(!rad[delta] && delta)
            continue;

        int b1 = h + rad[delta] ;
        int b2 = h - rad[delta] ;

        if(b1 % 2 ==0)
        {
            b1/=2;
            if(b1 <= h && b1>0)
                ++ nr;
        }
        if(delta == 0 )
            continue;
        if(b2 % 2 ==0)
        {
            b2/=2;
            if(b2 <= h && b2>0)
                ++ nr;
        }

    }
    return nr;
}

int main()
{
    f >> n >> m;

    --n;
    --m;

    for(i = 1 ; i <= 400 ; ++ i)
        rad[i * i] = i;

    for( h = 1 ; h <= n ; ++ h)
        for( w = 1 ; w <= m ; ++ w)
        {
            if(cate[w][h])
                cate[h][w]=cate[w][h];
            else
                cate[h][w]=numara(w,h);

            sol += 1LL * cate[h][w] * (n - h + 1) * (m - w + 1);

        }
    g << sol << '\n';

    return 0;

}