Pagini recente » Istoria paginii runda/splunge2 | Autentificare | Istoria paginii runda/gigel_si_nemuritorii | Istoria paginii runda/simulareidk/clasament | Cod sursa (job #31440)
Cod sursa(job #31440)
#include<stdio.h>
#define maxn 1001
long x[maxn],y[maxn],n,dx[maxn*maxn],dy[maxn*maxn];
void interclaseaza (long p, long q)
{long m=(p+q)/2;
long a1[maxn*maxn], a2[maxn*maxn],k1,k2,nr;
nr=0;
k1=p;
k2=m+1;
while (k1<=m && k2<=q)
{if(dy[k1]*dx[k2]>=dy[k2]*dx[k1]) {a1[++nr]=dx[k1];
a2[nr]=dy[k1];
k1++;}
else {a1[++nr]=dx[k2];
a2[nr]=dy[k2];
k2++;
}
}
while (k1<=m) {a1[++nr]=dx[k1];
a2[nr]=dy[k1];
k1++;}
while (k2<=q) {a1[++nr]=dx[k2];
a2[nr]=dy[k2];
k2++;
}
for(k1=p,k2=1;k1<=q;k1++,k2++)
{dx[k1]=a1[k2];
dy[k1]=a2[k2];
}
}
void sort(long p, long q)
{if(p!=q){sort(p,(p+q)/2);
sort((q+p)/2+1, q);
interclaseaza(p,q);
}
}
int main()
{long i,NR;
freopen("trapez.in","r",stdin);
scanf("%ld\n",&n);
for(i=1;i<=n;i++)
{scanf("%ld %ld\n",&x[i],&y[i]);}
long i1,i2,i3,i4,a,b,n2,nr1;
NR=0;
n2=0;
for(i1=1;i1<n;i1++)
for(i2=i1+1;i2<=n;i2++)
if(y[i1]>y[i2]) {dy[++n2]=y[i1]-y[i2];dx[n2]=x[i1]-x[i2]; }
else {dy[++n2]=y[i2]-y[i1];dx[n2]=x[i2]-x[i1];}
sort(1,n2);
i1=2;
while (i1<=n2)
{nr1=1;
while (dy[i1]*dx[i1-1]==dy[i1-1]*dx[i1] && i1<=n2) {i1++;nr1++;}
NR+=(nr1*(nr1-1))/2;
if (nr1==1) i1++;
}
freopen("trapez.out","w",stdout);
printf("%ld\n",NR);
return 0;}