Cod sursa(job #5076)

Utilizator zombie_testeala bala portocala si mandarina zombie_teste Data 9 ianuarie 2007 22:43:50
Problema Dreptunghiuri Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define NMax 402
#define filein "dreptunghiuri.in"
#define fileout "dreptunghiuri.out"

int m, n;
long long NR = 0;

int radical[NMax * NMax + 1];
int M[NMax + 1][NMax + 1];

void preproc()
{
	int i;

	for (i = 1; i < NMax; i++)
		radical[i * i] = i;
}

int nr_radacini(int h, int w, int a)
{
	int delta, x1, x2;

	delta = w*w - 4 * a * (h-a);
	if (delta < 0) return 0;

	if (radical[delta] || delta == 0)
	{
		x1 = (w-radical[delta]) / 2;
		x2 = (w+radical[delta]) / 2;
		if (x1 == x2)
			return (0 <= x1 && x1 < w);
		else
			return (0 <= x1 && x1 < w) + (0 <= x2 && x2 < w);
	}
	return 0;
}

void compute()
{
	int w, h, A, C, numar = 0;

	for (h = 1; h <= m; h++)
		for (w = 1; w <= n; w++)
		{
			if (h <= w || h > n)
			{
				M[h][w] = 0;
				for (A = 0; A < h; A++)
					M[h][w] += nr_radacini(h, w, A);
			}
			else
				M[h][w] = M[w][h];

			NR += (long long)M[h][w] * (m-h+1) * (n-w+1);

		}
}

int main()
{
	fscanf(fopen(filein, "r"), "%d %d", &m, &n);
	m--; n--;
	preproc();
	compute();
	fprintf(fopen(fileout, "w"), "%lld\n", NR);
}