Pagini recente » Cod sursa (job #433207) | Cod sursa (job #439700) | Cod sursa (job #22086) | Cod sursa (job #1116391) | Cod sursa (job #235885)
Cod sursa(job #235885)
#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;
}
void sanitize(fractie& x)
{
int c = 1;
if ((x.nr <= 0) && (x.nu <= 0)) { x.nr = -x.nr; x.nu = -x.nu; }
if (x.nu < 0) { x.nr = -x.nr; x.nu = -x.nu };
if (!(x.nu)) x.nr = 1;
if (!(x.nr)) x.nu = 1;
if (x.nu) c = cmmdc(abs(x.nr), abs(x.nu));
x.nr /= c;
x.nu /= c;
}
int hk(fractie x)
{
int mask;
const int SPICE1 = 9954, SPICE2 = 1356;
srand((x.nr + SPICE1) * (x.nu + SPICE2));
mask = ~(~0 << KEYLENGTH);
return rand() & mask;
}
fractie hash[1 << KEYLENGTH][80] = {};
int main()
{
unsigned int rasp = 0;
int N, x[NMAX] = {}, y[NMAX] = {};
int ii, jj, hllen = 0;
int key;
fractie *hl[1 << KEYLENGTH] = {}, **i, *j, *k, panta;
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 ( hash[key][0].nr == 1 )
hl[hllen++] = hash[key];
hash[key][++(hash[key][0].nr)] = panta;
}
for (i = hl; *i; ++i) {
for (j = (*i) + 1; (j -> nr || j -> nu); ++j)
for (k = j + 1; (k -> nr || k -> nu); ++k)
if ( (j -> nr == k -> nr) && (j -> nu == k -> nu) ) ++rasp;
}
printf("%u\n", rasp);
fclose(stdin);
fclose(stdout);
return 0;
}