Cod sursa(job #236435)

Utilizator Omega91Nicodei Eduard Omega91 Data 27 decembrie 2008 16:00:07
Problema Trapez Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
#include <math.h>
#include <stdlib.h>

const unsigned NMAX = 1005, KEYLENGTH = 16;
int SALT1 = 19, SALT2 = 34;

struct el { int nr; int nu; };

struct hash_el
{ el v; unsigned int count; };

inline bool fegal(el x, el y)
{
	return ((long long)x.nr * (long long)y.nu) == ((long long)x.nu * (long long)y.nr);
}

inline int hk(el x)
{
	//int mask = ~(~0 << KEYLENGTH);
	const long double A = 0.618033988749895L;
	//const double A = 0.123456879123;
	if (!x.nu) return 0;
	long double t = A * ((long double)x.nr / (long double)x.nu);
	const unsigned int M = 1 << KEYLENGTH;
	return floor( (t - floor(t)) * (M - 1) ) + 1;
	//return ((x.nr + SALT1) * (x.nu + SALT2)) & mask;
}

inline bool add(hash_el* ls, el x)
{
	unsigned int m = ls -> count, i;
	bool ok = false, added = false;
	for (i = 1; i <= m; ++i) {
		if ( fegal(ls[i].v, x) ) {
			added = true;
			++ls[i].count;
			if (ls[i].count == 2) ok = true;
			break;
		}
	}
	if (!added) {
		i = ++(ls[0].count);
		ls[i].count = 1;
		ls[i].v.nr = x.nr;
		ls[i].v.nu = x.nu;
	}
	if (ok && !((ls -> v).nr)) {
		(ls -> v).nr = 1;
		return 1;
	}
	else return 0;
}

hash_el hash[(1 << KEYLENGTH) + 1][20] = {}, *hl[(1 << KEYLENGTH) + 5] = {};

int main()
{
	unsigned int rasp = 0;
	int N, x[NMAX] = {}, y[NMAX] = {};
	int ii, jj, key, hllen = 0, k, m;
	//int nr, nu;
	el panta;
	hash_el **i, *j;
	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];
			key = hk(panta);
			if ( add(hash[key], panta) ) hl[hllen++] = hash[key];
		}
	for (i = hl; *i; ++i) {
		j = *i;
		m = j -> count;
		for (k = 1; k <= m; ++k)
			rasp += j[k].count * (j[k].count - 1) / 2;
	}

	printf("%u\n", rasp);

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