Cod sursa(job #1546705)

Utilizator vladrochianVlad Rochian vladrochian Data 8 decembrie 2015 17:13:44
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>

using namespace std;

const int N_MAX = 400;

int M, N;
int64_t ans;

int sqroot[N_MAX * N_MAX + 5];

int main() {
   for (int i = 1; i <= N_MAX; ++i)
      sqroot[i * i] = i;

   ifstream("dreptunghiuri.in") >> M >> N;
   --M; --N;

   for (int H = 1; H <= M; ++H)
      for (int W = 1; W <= N; ++W) {
         int crt = 1;
         for (int a = 1; a < W; ++a) {
            int delta = H * H - 4 * a * (W - a);
            if (delta < 0)
               continue;
            int rad = sqroot[delta];
            if (rad * rad != delta || ((H ^ rad) & 1))
               continue;

            if (rad == 0)
               ++crt;
            else if (rad < H)
               crt += 2;
         }
         ans += crt * (M - H + 1) * (N - W + 1);
      }

   ofstream("dreptunghiuri.out") << ans << "\n";
   return 0;
}