Cod sursa(job #1448492)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 7 iunie 2015 12:12:37
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
using namespace std;
ifstream f("dreptunghiuri.in");
ofstream g("dreptunghiuri.out");
int N,M;
long long ans;
int Sqrt[405*405];
void Solve(int H,int W)
{
    int res=0,aux=0;
    for(int i=0;i<=H;i++)
    {
        if(i==H/2 && H%2==0)
            aux=res;
        if((i>=H-H/2 && H%2==1) || (i>H-H/2 && H%2==0))
            break;
        int delta=W*W-4*(H-i)*i;
        if(delta!=0 && (delta<0 || Sqrt[delta]==0))
            continue;
        if((W-Sqrt[delta])%2==0 && (W-Sqrt[delta])/2>0 && (W-Sqrt[delta])/2<W)
            ++res;
        if(delta!=0 && (W+Sqrt[delta])%2==0 && (W+Sqrt[delta])/2>0 && (W+Sqrt[delta])/2<W)
            ++res;
    }
    int diff=res-aux;
    if(H%2==1)
        res*=2;
    else
        res=aux*2+diff;
    ++res;
    ans+=(N-H+1)*(M-W+1)*res;
}
int main()
{
    f>>N>>M;
    --N;
    --M;
    for(int i=1;i<=400;i++)
        Sqrt[i*i]=i;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            Solve(i,j);
    g<<ans<<"\n";
    return 0;
}