Cod sursa(job #70661)

Utilizator moga_florianFlorian MOGA moga_florian Data 6 iulie 2007 18:02:16
Problema Dreptunghiuri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<stdio.h>
#define Nmax 404

char solved[Nmax][Nmax];
int rad[170000];
long long cat[Nmax],sum[Nmax];

int main()
{
FILE *fin=fopen("dreptunghiuri.in","r"),
     *fout=fopen("dreptunghiuri.out","w");
     
int M,N,W,H,A,i,delta,C,s1,s2,ns;
fscanf(fin,"%d%d",&M,&N);

for(i=1; i*i<=160000; i++)
   rad[i*i]=i;

long long sol=0,crt;

for(H=1;H<M;H++)
  for(W=1;W<N;W++)
//     if(solved[H][W] == 0)
        {
        crt=0;
        if(H==7 && W==5)
           crt=0;
        
        for(A=1;A<H;A++)
          if(H-A < A && H-A>0)
           crt+=cat[H-A];
          else
           {
           delta= W*W - 4*A*(H-A);
           if(delta>=0 && rad[delta] || delta==0)
              {
              ns=0;
              //sol1
              C=W-rad[delta];
              if(C % 2 ==0 && C/2 > 0 && C/2 <= W )
                 {
                 crt++;
                 ns++;
                 s1=C/2;
                 }                               
              //sol2
              C=W+rad[delta];
              if(C%2==0 && C/2>0 && C/2<=W)
                 {
                 crt++;                         
                 ns++;
                 s2=C/2;
                 }
                 
              if(ns==2 && s1==s2)
                 crt--;                 
              }   
           cat[A]=crt-sum[A-1];
           sum[A]=crt;
           }
           
        crt++;           
        crt*= (M-H) * (N-W);                              
//        fprintf(fout,"(%d,%d)   -->   %d\n",H,W,crt);
        sol+=crt;     
        }
   
fprintf(fout,"%lld\n",sol);
fclose(fin);
fclose(fout);
return 0;    
}