Pagini recente » Cod sursa (job #2154477) | Cod sursa (job #361795) | Cod sursa (job #2162553) | Cod sursa (job #48161) | Cod sursa (job #364826)
Cod sursa(job #364826)
#include <stdio.h>
#include <stdlib.h>
#define N 1000000
#define M 1001
int c[N],d[N],vf;
int x[N],y[N];
int cmmdc(int a,int b)
{if(a%b==0)
return b;
else
return cmmdc(b,a%b);
}
void quick(int stanga, int dreapta)
{int st=stanga,dr=dreapta,pm=st+rand()%(dr-st+1),q=10000*c[pm]+d[pm],aux1,aux2;
while(st<dr)
{while(c[st]*10000+d[st]<q){st++;}
while(c[dr]*10000+d[dr]>q){dr--;}
if(st<=dr)
{aux1=c[st];c[st]=c[dr];c[dr]=aux1;
aux2=d[st];d[st]=d[dr];d[dr]=aux2;
st++;
dr--;
}
}
if(stanga<dr)
{quick(stanga,dr);
}
if(st<dreapta)
{quick(st,dreapta);
}
}
int main()
{freopen("trapez.in","r",stdin);
freopen("trapez.out","w",stdout);
int i,j,r,t,n,cmm;
scanf("%d",&n);
for (i=0;i<n;i++)
{scanf("%d %d",&x[i],&y[i]);}
r=t=0;
for (i=0;i<n-1;i++)
{for (j=i+1;j<n;j++)
{if(x[i]==x[j])
{r++;
}
else if(y[i]==y[j])
{t++;
}
else
{cmm=cmmdc(abs(x[i]-x[j]),abs(y[i]-y[j]));
c[vf]=abs(x[i]-x[j])/cmm;
d[vf]=abs(y[i]-y[j])/cmm;
if((x[i]-x[j])*(y[i]-y[j])<0)
{c[vf]*=-1;
}
vf++;
}
}
}
quick(0,vf-1);
int s=0;
for (i=0,j=0;i<vf;i++)
{if(c[i]==c[i+1]&d[i]==d[i+1])
{j++;}
else
{s+=(j*(j+1))/2;
j=0;
}
}
s+=r*(r-1)/2+t*(t-1)/2;
printf("%d",s);
return 0;
}