Pagini recente » Cod sursa (job #2668370) | Cod sursa (job #1441969) | Cod sursa (job #2554652) | Cod sursa (job #107877) | Cod sursa (job #443095)
Cod sursa(job #443095)
#include<stdio.h>
struct structura{long long x,y;};
structura p[1001],t;
double v[501501],aux;
long long n,poz=-1,nr,s,nroy;
void citire()
{
freopen("trapez.in","r",stdin);
int i;
scanf("%lld",&n);
for(i=1;i<=n;i++)
scanf("%lld%lld",&p[i].x,&p[i].y);
}
void swap(double &a,double &b)
{
aux=a;a=b;b=aux;
}
void panta()
{
int i,j;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
t.y=p[j].y-p[i].y;
t.x=p[j].x-p[i].x;
if(t.x!=0)
{
poz++;
v[poz]=(double)t.y/t.x;
}
else nroy++;
}
}
void DownHeap( int from, int to )
{
for( int son=2*from; son < to; from=son, son=2*from )
{
if( son < to-1 && v[son+1] > v[son] )
++son;
if( v[from] >= v[son] )
return;
swap( v[from], v[son] );
}
}
void HeapSort( int from, int to )
{
int i;
for( i=(to-from)/2; i >= 0; --i )
DownHeap( i, to );
while( to > from )
{
swap( v[from], v[to-1] );
--to;
DownHeap( from, to );
}
}
int main()
{
int i;
citire();
panta();
HeapSort(0,poz+1);
freopen("trapez.out","w",stdout);
aux=v[1];nr=1;
for(i=2;i<=poz;i++)
{
//printf("%df ",vect[i]);
if(v[i]==aux)
nr++;
else
{
s=s+nr*(nr-1)/2;
nr=1;
aux=v[i];
}
}
printf("%lld\n",s+nroy*(nroy-1)/2);
}