Cod sursa(job #235842)

Utilizator Omega91Nicodei Eduard Omega91 Data 25 decembrie 2008 23:56:16
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <math.h>
#include <stdlib.h>

const unsigned NMAX = 1005;
const unsigned RMAX = 600000, KEYLENGTH = 16;
	
struct fractie
{
	int nr, nu;
};

int cmmdc(int a, int b)
{
	int r = 1;
	while(r) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int hk(fractie& x)
{
	//double a;
	long mask;
	//const int BITS = sizeof(double) * 8;
	int c = 1;
	const int SPICE = 123;
	if ((x.nr <= 0) && (x.nu <= 0)) { x.nr = -x.nr; x.nu = -x.nu; }
	if (x.nu) c = cmmdc(abs(x.nr), abs(x.nu));
	x.nr /= c;
	x.nu /= c;
	srand((x.nr + SPICE) * x.nu);
	mask = ~(~0 << KEYLENGTH);
	return rand() & mask;
	/*a = (x.nr / c) / (x.nu / c);
	long b = a << 1;
	for (i = 0; i < BITS; ++i)
	
		if ( a & (1 << i) ) {
			mask = ~(~0 << KEYLENGTH) << i;
			return (a & mask) >> i;
		}*/
}

fractie hash[1 << KEYLENGTH][20] = {};

int main()
{
	unsigned int rasp = 0;
	int N, x[NMAX] = {}, y[NMAX] = {};
	int ii, jj, hllen = 0;
	int key;
	fractie *hl[RMAX] = {}, *hlmaxp, **i, *j, *k, panta;;
	
	freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);
	scanf("%d", &N);
	for (ii = 0; ii != N; ++ii)
		scanf("%d %d\n", &x[ii], &y[ii]);
	for (ii = 0; ii != N; ++ii)
		for (jj = ii + 1; jj != N; ++jj) {
			panta.nr = y[ii] - y[jj];
			panta.nu = x[ii] - x[jj];
			if (!panta.nu) panta.nr = 1;
			if (!panta.nr) panta.nu = 1;
			key = hk(panta);
			if ( hash[key] -> nu == 1 )
				hl[hllen++] = hash[key];
			hash[key][++(hash[key] -> nu)] = panta;
		}
	for (i = hl; *i; ++i) {
		hlmaxp = (*i)->nu + *i + 1;
		for (j = (*i) + 1; j < hlmaxp; ++j)
			for (k = j + 1; k < hlmaxp; ++k)
				if (j -> nr == k -> nr && j -> nu == k -> nu) ++rasp;
	}
	printf("%u\n", rasp);

	fclose(stdin);
	fclose(stdout);
	return 0;
}