Cod sursa(job #237472)

Utilizator Omega91Nicodei Eduard Omega91 Data 29 decembrie 2008 21:06:04
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <cstdio>
#include <math.h>
#include <stdlib.h>
#include <string.h>

const unsigned NMAX = 1005, KEYLENGTH = 16;

struct el { int nr, nu; unsigned int count; };

struct hash_el
{ el* p; unsigned int nr, alloc; bool added; };

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

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

inline int hk(el x)
{
	int mask = ~(~0 << KEYLENGTH);
	const int SALT1 = 9954, SALT2 = 1356;
	return ((x.nr + SALT1) * (x.nu + SALT2)) & mask;
}

inline bool add(hash_el& he, el x)
{
	const int K = 10;
	unsigned int m = he.nr, i;
	el *(&p) = he.p, *nl;
	bool ok = false;
	
	if (he.alloc <= (m + 1)) {
		if (he.alloc == 0) {
			p = new el [K];
			he.alloc = K;
		}
		else {
			nl = new el[m + K];
			memcpy(nl, p, sizeof(el) * m);
			delete[] p;
			p = nl;
			he.alloc = m + K;
		}
	}
	
	for (i = 0; i != m; ++i) {
		if ( (p[i].nr == x.nr) && (p[i].nu == x.nu) ) {
			++p[i].count;
			if (p[i].count == 2) ok = true;
			break;
		}
	}
	if (i == m) {
		i = he.nr++;
		p[i].count = 1;
		p[i].nr = x.nr;
		p[i].nu = x.nu;
	}
	if ( ok && !he.added) {
		he.added = true;
		return 1;
	}
	else return 0;
}

hash_el hash[(1 << KEYLENGTH) + 1] = {}, *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, *ls;
	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];
			sanitize(panta);
			key = hk(panta);
			if ( add(hash[key], panta) ) hl[hllen++] = &hash[key];
		}
	for (i = hl; *i; ++i) {
		j = *i;
		ls = j -> p;
		m = j -> nr;
		for (k = 0; k < m; ++k)
			rasp += ls[k].count * (ls[k].count - 1) / 2;
	}

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

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