Cod sursa(job #792241)

Utilizator visanrVisan Radu visanr Data 26 septembrie 2012 19:49:33
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <cstdlib>
using namespace std;

#define nmax 1010

int N, M;
long long ans;
int rad[nmax * nmax];


int Solve(int H, int W)
{
    int now = 1, D, x1, x2, i;
    for(i = 1; i < H; i++)
    {
        D = W * W - 4 * i * (H - i);
        if(D == 0 && !(W % 2))
        {
            now ++;
            continue;
        }
        if(D <= 0 || rad[D] == 0)
            continue;
        x1 = W - rad[D]; x2 = W + rad[D];
        if(x1 >= 2 && x1 < 2 * W && !(x1 % 2)) now ++;
        if(x2 >= 2 && x2 < 2 * W && !(x2 % 2)) now ++;
    }
    return now;
}

int main()
{
    freopen("dreptunghiuri.in", "r", stdin);
    freopen("dreptunghiuri.out", "w", stdout);
    int i, j;
    scanf("%i %i", &N, &M);
    for(i = 1; i < nmax; i++)
        rad[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);
    printf("%lld\n", ans);
    return 0;
}