Pagini recente » Cod sursa (job #1116397) | Cod sursa (job #1116599) | Cod sursa (job #2920248) | Cod sursa (job #2386198) | Cod sursa (job #237474)
Cod sursa(job #237474)
#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; };
inline bool fegal(el x, el y)
{
return ((long long)x.nr * (long long)y.nu) == ((long long)x.nu * (long long)y.nr);
}
inline int hk(el x)
{
const long double A = 0.618033988749895L;
if (!x.nu) return 0;
double t = A * ((double)x.nr / (double)x.nu);
const unsigned int M = 1 << KEYLENGTH;
return floor( (t - floor(t)) * (M - 1) ) + 1;
}
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 ( fegal(p[i], x) ) {
++p[i].count;
if (p[i].count == 2) ok = true;
break;
}
}
if (i == m) {
i = he.nr++;
p[i].count = 1;
p[i] = x;
}
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];
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;
}