Cod sursa(job #236194)

Utilizator Omega91Nicodei Eduard Omega91 Data 26 decembrie 2008 22:09:33
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <math.h>
#include <stdlib.h>

const unsigned NMAX = 1005, KEYLENGTH = 16;;
int SALT = 725;

struct hash_el
{ double v; hash_el* p; };

inline int hk(double x)
{
	int mask = ~(~0 << KEYLENGTH);
	return long((x + SALT) * (1 << 5)) & mask;
}

int main()
{
	unsigned int rasp = 0;
	int N, x[NMAX] = {}, y[NMAX] = {};
	int ii, jj, i, key;
	double panta, nr, nu, av;
	hash_el *hash[1 << KEYLENGTH] = {}, *nsl, *a, *b;
	
	
	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) {
			nr = y[jj] - y[ii];
			nu = x[jj] - x[ii];
			if (!nu) {
				key = 0;
				panta = 4000000000;
			}
			else {
				panta = nr / nu;
				key = hk(panta);
			}
			nsl = new hash_el;
			nsl -> v = panta;
			nsl -> p = hash[key];
			hash[key] = nsl;
		}
	for (i = 0; i < (1 << KEYLENGTH); ++i) {
		a = hash[i];
		while(a) {
			b = a;
			av = a -> v;
			while ( (b = b -> p) ) if (av == (b -> v)) ++rasp;
			a = a -> p;
		}
	}
	printf("%u\n", rasp);

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