Cod sursa(job #442182)

Utilizator vladiiIonescu Vlad vladii Data 13 aprilie 2010 22:43:58
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

int N, M, H, W;
int rad[400*400];
long long sol, p, Nr[401][401];
    
int main() {
    fstream f1, f2; f1.open("dreptunghiuri.in", ios::in); f2.open("dreptunghiuri.out", ios::out);
    int i, j, q, A, D;
    f1>>M>>N;
    for(i=1; i<N; i++) {
         for(j=1; j<M; j++) {
              //aflu numarul de dreptunghiuri inscrise
              //intr-un dreptunghi mare de laturi H = i, W = j
              H = i; W = j; p = 1;
              if(Nr[W][H]) { sol+=(Nr[W][H]*(N-H)*(M-W)); }
              else {
                   for(A=1; A<H; A++) {
                        D=W*W - 4*A*(H - A);
                        if(D>=0) { 
                                 if(rad[D]) { q=rad[D]; }
                                 else { q=(int)sqrt(D); rad[D]=q; }
                        }
                        if(D>=0 && q*q==D) {
                             if((W - q)%2==0 && ((W - q)>>1)>0 && ((W - q)>>1)<W) {
                                  p++;
                             }
                             if((W + q)%2==0 && ((W + q)>>1)>0 && ((W + q)>>1)<W) {
                                  p++;
                             }
                             if((W - q)%2==0 && (W + q)%2==0 && ((W - q)>>1)>0 && ((W + q)>>1)>0 && ((W - q)>>1)<W && ((W + q)>>1)<W && ((W - q)>>1)==((W + q)>>1)) {
                                  p--;
                             }
                        }
                   }
                   Nr[H][W]=p;
                   p *= ((N-H)*(M-W));
                   sol+=p;
              }
         }
    }
    f2<<sol<<'\n';
    f1.close(); f2.close();
    return 0;
}