Cod sursa(job #791346)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 23 septembrie 2012 20:52:08
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#define NM 1010

using namespace std;

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

int N,M,i,j;
long long ANS=0;
int Sqrt[NM*NM];

int Solve (int H, int W)
{
    int ANS=0;
    int D,X1,X2;
    for (int k=1; k<H; k++)
    {
        D=W*W-4*k*(H-k);
        if (D==0 && W%2==0)
        {
            ANS++;
            continue;
        }
        if (D<=0) continue;
        if (Sqrt[D]==0) continue;
        X1=W-Sqrt[D];
        X2=W+Sqrt[D];

        if (X1>=2 && X1<2*W && X1%2==0) ANS++;
        if (X2>=2 && X2<2*W && X2%2==0) ANS++;
    }

    return ANS+1;
}

int main ()
{
    f >> N >> M;

    for (i=1; i<NM; i++)
        Sqrt[i*i]=i;

    for (i=2; i<=N; i++)
        for (j=2; j<=M; j++)
            ANS+=1LL*Solve(i-1,j-1)*(N-i+1)*(M-j+1);

    g << ANS << '\n';

    f.close();
    g.close();
    return 0;
}