Cod sursa(job #1156955)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 28 martie 2014 10:03:51
Problema Dreptunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <map>
using namespace std;

map <int,int> sq;

int analyze(int h,int w)
{
    //cout<<"\nANALYZE:"<<h<<' '<<w<<'\n';
    int a,delta,sqd,b;
    int ans=0;

    map <int,int>::iterator it;

    for (a=1;a<=h;a++)
    {
        //cout<<"a="<<a<<' ';
        delta=w*w+4*(a*a-h*a);
        //cout<<"delta="<<delta;
        it=sq.find(delta);
        if (it!=sq.end())
        {
            sqd=(*it).second;
            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,sum,i;
int 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.insert(make_pair(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;
}