Cod sursa(job #236353)

Utilizator Omega91Nicodei Eduard Omega91 Data 27 decembrie 2008 11:56:53
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <math.h>
#include <stdlib.h>

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

struct hash_el
{ double v; unsigned int nr; };

inline int hk(double x)
{
	//int mask = ~(~0 << KEYLENGTH);
	double A = 0.618;
	double t = A * x;
	unsigned int M = 1 << KEYLENGTH;
	return floor( (t - floor(t)) * (M - 1) ) + 1;
}

bool add(hash_el* hash, double x)
{
	hash_el* i;
	unsigned int* q;
	bool bad = false, ok = false, added = false;
	for (i = hash; i -> nr; ++i) {
		q = &(i -> nr);
		if (*q == 2) bad = true;
		if (i -> v == x) {
			if (*q == 1) ok = true;
			++(i -> nr);
			added = true;
		}
	}
	if (!added) {
		++(i -> nr);
		i -> v = x;
	}
	return (!bad) && ok;
}

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

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

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