Cod sursa(job #236111)

Utilizator Omega91Nicodei Eduard Omega91 Data 26 decembrie 2008 20:17:36
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 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;
}

void sanitize(fractie& x)
{
	int c = 1;
	if ((x.nr <= 0) && (x.nu <= 0)) { x.nr = -x.nr; x.nu = -x.nu; }
	if (x.nu < 0) { x.nr = -x.nr; x.nu = -x.nu; };
	if (!(x.nu)) x.nr = 1;
	if (!(x.nr)) x.nu = 1;
	if (x.nu) c = cmmdc(abs(x.nr), abs(x.nu));
	x.nr /= c;
	x.nu /= c;
}

int hk(fractie x)
{
	int mask;
	const int SPICE1 = 9954, SPICE2 = 1356;
	srand((x.nr + SPICE1) * (x.nu + SPICE2));
	mask = ~(~0 << KEYLENGTH);
	return rand() & mask;
}

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

int main()
{
	unsigned int rasp = 0;
	int N, x[NMAX] = {}, y[NMAX] = {};
	int ii, jj, hllen = 0;
	int key;
	fractie *hl[1 << KEYLENGTH] = {}, **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[jj] - y[ii];
			panta.nu = x[jj] - x[ii];
			sanitize(panta);
			key = hk(panta);
			/*if ( hash[key][0].nr == 1 )
				hl[hllen++] = hash[key];
			hash[key][++(hash[key][0].nr)] = panta;*/
		}
	/*for (i = hl; *i; ++i) {
		for (j = (*i) + 1; (j -> nr || j -> nu); ++j)
			for (k = j + 1; (k -> nr || k -> nu); ++k)
				if ( (j -> nr == k -> nr) && (j -> nu == k -> nu) ) ++rasp;
	}*/
	printf("%u\n", rasp);

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