Cod sursa(job #344507)

Utilizator CezarMocanCezar Mocan CezarMocan Data 30 august 2009 13:41:37
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.14 kb
#include <cstdio>
#include <cstring>
#include <math.h>

using namespace std;

int n, m, i, w, h, l1, l2, L1, L2;
int a, b, c, nr;
int delta;
int x1, x2;
int rad[801 * 801];
long long sol;
int rez[410][410];

inline void swap(int &n, int &m) {
	int aux;
	aux = n; n = m; m = aux;
}

int main() {
	freopen("dreptunghiuri.in", "r", stdin);
	freopen("dreptunghiuri.out", "w", stdout);

	scanf("%d%d", &n, &m);

	if (n > m)
		swap(n, m);

	for (i = 0; i <= 800; i++)
		rad[i * i] = i;

	for (w = 2; w <= n; w++)
		for (h = w; h <= m; h++) {
			nr = 0;
			for (l1 = 0; l1 < h - 1; l1++) {
				l2 = h - l1 - 1;
				a = 2;
				b = -2 * (w - 1);
				c = 2 * l1 * l2;
				delta = b * b - 4 * a * c;
				if (delta < 0)
					continue;
				if (delta > 0 && rad[delta] == 0)
					continue;
				delta = rad[delta];


				x1 = (-b + delta) / 4;
				x2 = (-b - delta) / 4;

				if (x1 > 0 && x1 < w)
					nr++;
				if (x2 != x1 && x2 > 0 && x2 < w)
					nr++;
			}
			if (w == h)
				rez[w][h] = nr;
			else
				rez[w][h] = rez[h][w] = nr;
		}

	for (w = 2; w <= n; w++)
		for (h = 2; h <= m; h++)
			sol += rez[w][h] * (n - w + 1) * (m - h + 1);

	printf("%lld\n", sol);
		

	return 0;
}