Cod sursa(job #1139975)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 11 martie 2014 17:26:21
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

int sqr[401 * 401];

int solve( int H, int W )
{
    int sol = 0;

    for ( int A = 1; A <= H; ++A )
    {
        int delta = W * W - 4 * A * ( H - A );

        if ( delta < 0 )
                continue;

        if ( delta == 0 )
        {
            if ( W % 2 == 0 )
                    sol++;

            continue;
        }

        if ( delta > 0 )
        {
            delta = sqr[ delta ];

            if ( delta == 0 ) continue;

            if ( ( W + delta ) % 2 == 0 && 1 <= ( W + delta ) / 2 && ( W + delta ) / 2 <= W  )
                    sol++;

            if ( ( W - delta ) % 2 == 0 && 1 <= ( W - delta ) / 2 && ( W - delta ) / 2 <= W  )
                    sol++;
        }
    }

    return sol;
}

int N, M;

int main()
{
    ifstream f("dreptunghiuri.in");
    ofstream g("dreptunghiuri.out");

    f >> N >> M;

    N--;
    M--;

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

    long long sol = 0;

    for ( int H = 1; H <= N; ++H )
            for ( int W = 1; W <= M; ++W )
                    sol += 1LL * solve( H, W ) * ( N - H + 1 ) * ( M - W + 1 );

    g << sol;

    return 0;
}