Cod sursa(job #2277435)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 6 noiembrie 2018 11:23:29
Problema Dreptunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>

using namespace std;

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

int N, M;
int sq[160005];
long long sol;

void Init()
{
    fin >> N >> M;
    N--, M--;

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

}

long long Compute(int h, int w)
{
    long long ans = 0;

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

        if(delta == 0)
        {
            int x = -b / (2 * a);

            if(!(-b % (2 * a)) && 0 <= x && x < w) ///x intreg intre 0 si w
                ans++;
        }
        else if(delta > 0)
        {
            int root = sq[delta];

            if(root)
            {
                int x1 = (-b + root) / (2 * a);
                int x2 = (-b - root) / (2 * a);

                if(!((-b + root) % (2 * a)) && 0 <= x1 && x1 < w) ///x1 intreg intre 0 si w
                    ans++;
                if(!((-b - root) % (2 * a)) && 0 <= x2 && x2 < w) ///x1 intreg intre 0 si w
                    ans++;
            }
        }
    }

    return ans;
}

int main()
{
    Init();

    for(int h = 1; h <= N; h++)
        for(int w = 1; w <= M; w++)
            sol += Compute(h, w) * (N - h + 1) * (M - w + 1);

    fout << sol << '\n';

    return 0;
}