Cod sursa(job #792236)

Utilizator visanrVisan Radu visanr Data 26 septembrie 2012 19:44:50
Problema Dreptunghiuri Scor 0
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]) / 2; x2 = (W + rad[D]) / 2;
        if(x1 >= 1 && x1 < W && !(x1 % 2)) now ++;
        if(x2 >= 1 && x2 < 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;
}