Pagini recente » Cod sursa (job #596772) | Cod sursa (job #1777950) | Cod sursa (job #794107) | Cod sursa (job #2702044) | Cod sursa (job #236366)
Cod sursa(job #236366)
#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);
const double A = 0.618;
double t = A * x;
const 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;
break;
}
}
if (!added) {
++(i -> nr);
i -> v = x;
}
return (!bad) && ok;
}
hash_el hash[(1 << KEYLENGTH) + 5][8] = {};
int main()
{
unsigned int rasp = 0;
int N, x[NMAX] = {}, y[NMAX] = {};
int ii, jj, key, hllen = 0, t;
double panta, nr, nu;
hash_el *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) {
j = *i;
t = 1;
while(t) {
t = (j++) -> nr;
rasp += (t - 1) * t / 2;
}
}
printf("%u\n", rasp);
fclose(stdin);
fclose(stdout);
return 0;
}