Cod sursa(job #2292391)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 29 noiembrie 2018 14:48:47
Problema Dreptunghiuri Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <iostream>

using namespace std;
int root[160001];
int main()
{
    FILE *fin=fopen ("dreptunghiuri.in","r");
    FILE *fout=fopen ("dreptunghiuri.out","w");
    int n,m,i,sol,fr,h,w,dh,delta,r;
    fscanf (fin,"%d%d",&n,&m);
    root[1]=1;
    for (i=2;i<=160000;i++){
        if ((root[i-1]+1)*(root[i-1]+1)==i)
            root[i]=root[i-1]+1;
        else root[i]=root[i-1];
    }
    sol=0;
    for (h=1;h<n;h++){
        for (w=h;w<m;w++){
            fr=0;
            for (dh=0;dh<h;dh++){ // dh = lungime
                delta=w*w - 4*dh*(h-dh);
                if (root[delta]*root[delta]!=delta || (w&1)!=(root[delta]&1))
                    continue; // delta nu e pp sau rad nu in Z

                r=(w+root[delta])/2;
                if (0<=r && r<w)
                    fr++;
                r=(w-root[delta])/2;
                if (0<=r && r<w && root[delta])
                    fr++;
            }
            //printf ("%d\n",fr);
            if (w!=h)
                sol= sol + 2*fr*(n-h)*(m-w); // 2 pt ca h,w = w,h
            else
                sol= sol + fr*(n-h)*(m-w);
        }
    }
    fprintf (fout,"%d",sol);
    return 0;
}