Pagini recente » Cod sursa (job #448238) | Cod sursa (job #425838) | Cod sursa (job #2421068) | Cod sursa (job #827562) | Cod sursa (job #41298)
Cod sursa(job #41298)
#include <stdio.h>
#include <math.h>
#define NMAX 1091
#define CMAX 1101*(1001-1)/2
typedef struct punct
{
long x, y;
};
int n;
punct p[NMAX];
long double c[CMAX];
long h;
long long count;
inline long double abs(long double a)
{
if(a > 0)
return a;
return (-a);
}
void read()
{
int i;
scanf("%d\n", &n);
for(i = 0; i < n; ++i)
{
scanf("%ld %ld\n", &p[i].x, &p[i].y);
}
}
void fa_perechi()
{
int i, j;
long double nextx, nexty;
for(i = 0; i < n; ++i)
for(j = i+1; j < n; ++j)
{
nextx = (p[i].x - p[j].x);
nexty = (p[i].y - p[j].y);
if(nexty == 0)
{
++count;
}
else
{
nextx = (long double)nextx/nexty;
c[h++] = nextx;
//floor(nextx*1000 000 000 000)/1000000000000;
}
}
count = count * (count-1) / 2;
}
long divide(long p, long q)
{
long st = p, dr = q;
long double x = c[p];
while(st < dr)
{
while((st < dr) && c[dr] <= x) --dr;
c[st] = c[dr];
while((st < dr) && c[st] >= x) ++st;
c[dr] = c[st];
}
c[st] = x;
return st;
}
void qsort(long p, long q)
{
long m = divide(p, q);
if(m > p)
qsort(p, m-1);
if(m < q)
qsort(m+1, q);
}
void solve()
{
long i;
long double aux;
int nr = 1;
aux = c[0];
for(i = 1; i < h; ++i)
{
if(aux == c[i])
{
++nr;
}
else
{
if(nr > 1)
count += (nr*(nr-1)/2);
nr = 1;
aux = c[i];
}
}
}
int main()
{
freopen("trapez.in", "r", stdin);
freopen("trapez.out", "w", stdout);
read();
fa_perechi();
qsort(0, h-1);
solve();
printf("%lld\n", count);
fclose(stdin);
fclose(stdout);
return 0;
}