Cod sursa(job #1083441)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 15 ianuarie 2014 23:29:43
Problema Dreptunghiuri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <cmath>

#define e 0.000001

using namespace std;

ifstream fin("dreptunghiuri.in");
ofstream fout("dreptunghiuri.out");

double SQRT[1600000];
int ans[401][401];

int n,m,sum;
long long total;

int quadratic_eq (int x, int X, int Y)
{
    int sum = 0;
    int wh = 4*x*x - 4*X*x + Y*Y;

    if (wh < 0)
        return 0;

    if (SQRT[wh] == 0)
    {
        SQRT[wh] = sqrt(wh);
    }
                if (SQRT[wh])
                {
                    double root = (Y+SQRT[wh])/2;
                    if (root == int(root))
                    {
                        ++sum;
                    }

                    root = (Y-SQRT[wh])/2;
                    if (root==int(root))
                    {
                        ++sum;
                    }
                }

                else if (SQRT[wh]==0)
                {
                    if (!(Y&1))
                        ++sum;
                }
     return sum;
}

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

    for (int X=1; X<n; ++X)
        for (int Y=1; Y<m; ++Y)
    {
        if (ans[X][Y]!=0)
        {
            total += (n-X)*(m-Y)*ans[X][Y];
            continue;
        }

        for (int x=1; x <= X/2; ++x)
            {
                ans[X][Y] += quadratic_eq (x,X,Y);
            }

        ans[X][Y] = ans[X][Y]*2 +1;

        if (X%2==0)
        {
            ans[X][Y] -= quadratic_eq(X/2,X,Y);
        }

        total += (n-X)*(m-Y)*ans[X][Y];
    }

    fout<<total;
}