Pagini recente » Cod sursa (job #2131391) | Cod sursa (job #417386) | Statistici Duta Marius (misterdutamarius) | Cod sursa (job #308224) | Cod sursa (job #131026)
Cod sursa(job #131026)
#include <stdio.h>
#define NMAX 1001
#define NMAX2 500010
int n, nr;
struct PANTA
{
long long y, x;
};
PANTA a[NMAX];
PANTA m[NMAX2];
int partitie(int st, int dr)
{
int i, j;
PANTA pivot, aux;
pivot = m[(st+dr) / 2];
i = st - 1;
j = dr + 1;
while (1)
{
do {++i;} while ( m[i].y * pivot.x < m[i].x * pivot.y);
do {--j;} while ( m[j].y * pivot.x > m[j].x * pivot.y);
if ( i < j)
{
aux = m[i];
m[i] = m[j];
m[j] = aux;
}
else
return j;
}
}
void sort(int st, int dr)
{
int m;
if ( st < dr)
{
m = partitie(st, dr);
sort(st, m);
sort(m+1, dr);
}
}
int main()
{
int i, j;
long long rez = 0, l;
freopen("trapez.in", "r", stdin);
freopen("trapez.out", "w", stdout);
scanf("%d", &n);
for ( i = 1; i <= n; i++)
{
scanf("%d %d", &a[i].x, &a[i].y);
for ( j = 1; j < i; j++)
{
m[++nr].x = a[i].x - a[j].x;
m[nr].y = a[i].y - a[j].y;
if ( m[nr].x < 0)
{
m[nr].x *= -1;
m[nr].y *= -1;
}
}
}
sort(1, nr);
m[nr+1].x = 1000;
for ( i = 1; i <= nr; )
{
for ( j = i; m[j].y * m[j+1].x == m[j].x * m[j+1].y && j <= nr; j++);
if ( i != j)
{
l = j - i + 1;
rez += l*(l-1) / 2;
i = j;
}
else
i++;
}
printf("%lld", rez);
return 0;
}