Cod sursa(job #547896)

Utilizator savimSerban Andrei Stan savim Data 6 martie 2011 19:54:00
Problema Dreptunghiuri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>
#include <math.h>

#define MAX_N 410

int n, m;
int square_root[MAX_N * MAX_N];
int nr[MAX_N][MAX_N]; //numarul de dreptunghiuri dintr-un caroiaj ixj, care au punctele pe laturile caroiajului

long long sol;

inline int dist(int x1, int y1, int x2, int y2) {
	return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}

inline bool ok(int x, int lim) {
	if (1 <= x && x < lim)
		return true;
	return false;
}

void compute_nr() {
	for (int i = 1; i <= n * n; i++)
		square_root[i] = sqrt(i);

	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++) {
			nr[i][j] = 1; //dreptunghiul i * j

			for (int k = 1; k < j; k++) { //mi-am fixat dreptunghiul prin coloanele k si j - k
    			int a = 1;
				int b = -i;
				int c = k * (j - k);

				int delta = b * b - 4 * a * c;

				if (delta >= 0) {
					int rad = square_root[delta];

					if (delta == rad * rad) {
						int up = -b - rad;
						if (up % (2 * a) == 0) 		
							nr[i][j] += ok(up / (2 * a), i);
	
						if (delta) {
							up = -b + rad;
							if (up % (2 * a) == 0)
								nr[i][j] += ok(up / (2 * a), i);
						}
					} 
				}
			}

			sol = sol + 1LL * (n - i) * (m - j) * nr[i][j];
		}

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

int main() {

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

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

	return 0;
}