Cod sursa(job #193)

Utilizator MariusMarius Stroe Marius Data 6 decembrie 2006 19:17:23
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <cmath>
using namespace std;

const char iname[] = "dreptunghiuri.in";
const char oname[] = "dreptunghiuri.out";

typedef unsigned long long u64;

#define MAX_L 400

int rad[MAX_L * MAX_L + 1];

u64 sum[MAX_L + 1][MAX_L + 1];


int main(void)
{
	int m;
	int n;
	int cnt = 0;
	u64 result = 0;

	int d, r, q;
	double z;
	ifstream fin(iname);

	fin >> m >> n;
	for (d = 1; d <= MAX_L * MAX_L; ++d) {
		z = sqrt(double(d));
		if (z != int(z))
			rad[d] = int(1e5);
		else
			rad[d] = int(z);
	}
	for (int h = 1; h < m; ++h)
		for (int w = 1; w < n; ++w) {
			if (sum[h][w] > 0) {
				result += sum[h][w];
				continue;
			}
			cnt = 1;
			for (int i = 1; i <= h >> 1; ++i) {
				d = w*w - 4*i*(h-i);
				if (d < 0)
					continue;
				r = (w + rad[d]) >> 1;
				if (0 < r && r < w)
					cnt += 1 + (i + i < h);
				if (rad[d] > 0) {
					q = (w - rad[d]) >> 1;
						if (0 < q && q < w)
							cnt += 1 + (i + i < h);
				}
			}
			sum[h][w] = (u64)cnt * (m-h) * (n-w);
			sum[w][h] = (u64)cnt * (m-w) * (n-h);
			result += sum[h][w];
		}
	ofstream fout(oname);
	fout << result << '\n';

	fin.close();
	fout.close();
	return 0;
}