Pagini recente » Cod sursa (job #41884) | 02local11 | Cod sursa (job #531937) | Cod sursa (job #314927) | Cod sursa (job #214575)
Cod sursa(job #214575)
#include <stdio.h>
#define nmax 1005
#define inf 100
#define pr(x) fprintf(stderr,"%d ",x)
struct point
{
int x, y;
};
struct fractie
{
int numitor, numarator;
};
int n, nrp;
point p [nmax];
fractie pnt [nmax*nmax];
void scan ()
{
int i;
scanf ("%d", &n);
for (i=1; i<=n; ++i)
scanf ("%d%d", &p [i].x, &p [i].y);
}
int cmmdc (int a, int b)
{
int r;
while (b)
{
r=a%b;
a=b;
b=r;
}
return a;
}
void pante ()
{
int i, j, a;
for (i=1; i<=n; ++i)
for (j=i+1; j<=n; ++j)
{
pnt [++nrp].numitor=p [i].x - p [j].x;
pnt [nrp].numarator=p [i].y - p [j].y;
a=cmmdc (pnt [nrp].numitor, pnt [nrp].numarator);
pnt [nrp].numitor/=a;
pnt [nrp].numarator/=a;
if (pnt [nrp].numitor < 0)
{
pnt [nrp].numitor*=-1;
pnt [nrp].numarator*=-1;
}
}
}
int partitie (int st, int dr)
{
int i, j;
fractie aux, piv;
i=st-1;
j=dr+1;
piv=pnt [(st+dr)/2];
while (1)
{
do {i++;} while ((pnt [i].numitor < piv.numitor) || (pnt [i].numitor == piv.numitor && pnt [i].numarator < piv.numarator));
do {j--;} while ((pnt [j].numitor > piv.numitor) || (pnt [j].numitor == piv.numitor && pnt [j].numarator > piv.numarator));
if (i < j)
{
aux=pnt [i];
pnt [i]=pnt [j];
pnt [j]=aux;
}
else
return j;
}
}
void quicks (int st, int dr)
{
if (st < dr)
{
int p=partitie (st, dr);
quicks (st, p);
quicks (p+1, dr);
}
}
int trapez ()
{
int i, m, s=0;
for (i=1; i<=nrp; i)
{
m=i;
do
{
++i;
} while (pnt [i].numitor == pnt [i+1].numitor && pnt [i].numarator == pnt [i+1].numarator && i < nrp);
m=i-m;
if (m > 1)
s+=(m-1)*m/2;
}
return s;
}
int main ()
{
freopen ("trapez.in", "r", stdin);
freopen ("trapez.out", "w", stdout);
scan ();
pante ();
quicks (1, nrp);
printf ("%d", trapez ());
return 0;
}