Cod sursa(job #2277427)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 6 noiembrie 2018 11:13:26
Problema Dreptunghiuri Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>

using namespace std;

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

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

int main()
{
    fin >> N >> M;
    N--, M--;

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

    for(int h = 1; h <= N; h++)
        for(int w = h; w <= M; w++)
        {
            int 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++;
                    }
                }
            }

            if(h == w)
                sol += 1LL * ans * (N - h + 1) * (M - w + 1);
            else
                sol += 2LL * ans * (N - h + 1) * (M - w + 1);
        }

    fout << sol << '\n';

    return 0;
}