Cod sursa(job #1156965)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 28 martie 2014 10:12:56
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <fstream>
using namespace std;

int sq[200005];
long long analyze(int fh,int fw)
{
    //cout<<"\nANALYZE:"<<fh<<' '<<fw<<'\n';
    long long a,delta,sqd,b,h,w,ax;
    h=fh;
    w=fw;
    long long ans=0;

    for (a=1;a<=h;a++)
    {
        //cout<<"a="<<a<<' ';
        delta=w*w+4*(a*a-h*a);
        //cout<<"delta="<<delta;
        if (delta>0)
            ax=sq[delta];
        else
            ax=0;
        //cout<<" ax="<<ax;
        if ((ax!=0)||(delta==0))
        {
            sqd=ax;
            b=w+sqd;
            if (b%2==0)
            {
                b=b/2;
                //cout<<" b="<<b<<' ';
                if ((b>0)&&(b<=w))
                    ans++;
            }
            b=w-sqd;
            if ((b%2==0)&&(sqd!=0))
            {
                b=b/2;
                //cout<<" b="<<b<<' ';
                if ((b>0)&&(b<=w))
                    ans++;
            }
        }
        //cout<<'\n';
    }

    return ans;
}

int nl,nc,h,w,i;
long long sum;
long long m[505][505];

int main(void)
{
    FILE * f;
    f=fopen("dreptunghiuri.in","r");
    ofstream g("dreptunghiuri.out");
    fscanf(f,"%d%d",&nl,&nc);
    nl--;nc--;

    for (i=0;i<=nc;i++)
        sq[i*i]=i;

    for (h=1;h<=nl;h++)
        for (w=1;w<=nc;w++)
        {
            if ((h>w)&&(m[w][h]!=0))
                m[h][w]=m[w][h];
            else
                m[h][w]=analyze(h,w);
            //cout<<"m["<<h<<"]["<<w<<"]="<<m[h][w]<<'\n';
            sum=sum+m[h][w]*(nl-h+1)*(nc-w+1);
        }
    g<<sum<<'\n';
    return 0;
}