Pagini recente » Cod sursa (job #17835) | Cod sursa (job #1769193) | Cod sursa (job #22917) | Cod sursa (job #324548) | Cod sursa (job #235781)
Cod sursa(job #235781)
#include <cstdio>
#include <math.h>
#include <stdlib.h>
const unsigned NMAX = 1005;
const unsigned RMAX = 600000, KEYLENGTH = 16;
struct fractie
{
int nr, nu;
};
int cmmdc(int a, int b)
{
int r = 1;
while(r) {
r = a % b;
a = b;
b = r;
}
return a;
}
int hk(fractie x)
{
//double a;
long mask;
//const int BITS = sizeof(double) * 8;
int c = 1;
const int SPICE = 123;
if (x.nu) c = cmmdc (abs(x.nr), abs(x.nu));
x.nr /= c;
x.nu /= c;
srand(x.nr * (x.nu + SPICE));
mask = ~(~0 << KEYLENGTH);
return rand() & mask;
/*a = (x.nr / c) / (x.nu / c);
long b = a << 1;
for (i = 0; i < BITS; ++i)
if ( a & (1 << i) ) {
mask = ~(~0 << KEYLENGTH) << i;
return (a & mask) >> i;
}*/
}
fractie hash[1 << KEYLENGTH][20] = {}, panta;
int main()
{
unsigned int rasp = 0;
int N, x[NMAX], y[NMAX];
int ii, jj, hllen = 0;
int key;
fractie *hl[RMAX] = {}, *hlmaxp, **i, *j, *k;
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[ii] - y[jj];
panta.nu = x[ii] - x[jj];
if (!panta.nu) panta.nr = 1;
if (!panta.nr) panta.nu = 1;
key = hk(panta);
if ( hash[key] -> nu == 1 ) hl[hllen++] = hash[key];
hash[key][++(hash[key] -> nu)] = panta;
}
for (i = hl; *i; ++i) {
hlmaxp = (*i)->nu + *i + 1;
for (j = (*i) + 1; j != hlmaxp; ++j)
for (k = j + 1; k != hlmaxp; ++k)
if (j -> nr == k -> nr && j -> nu == k -> nu) ++rasp;
}
printf("%u\n", rasp);
fclose(stdin);
fclose(stdout);
return 0;
}