Pagini recente » Cod sursa (job #1888002) | Cod sursa (job #2636619) | Cod sursa (job #760172) | Cod sursa (job #53684) | Cod sursa (job #176688)
Cod sursa(job #176688)
#include <cstdio>
typedef struct Tfractie{
int p,q;}fractie;
typedef struct Tpunct{
int x,y;}punct;
punct v[1001];
fractie a[500001];
int n,nr,m;
int modul(int x){
return (x>=0?x:-x);
}
int cmmdc(int a,int b){
if (!b) return a;
int r=a%b;
while (r>0) {a=b;
b=r;
r=a%b;}
return b;
}
void simplifica(fractie &f){
int d=cmmdc(modul(f.p),modul(f.q));
f.p/=d;
f.q/=d;
}
void qsort(int ls,int ld){
int i=ls,j=ld,p=a[(ls+ld)/2].p,q=a[(ls+ld)/2].q;
do {while (a[i].p*q<a[i].q*p) ++i;
while (p*a[j].q<q*a[j].p) --j;
if (i<=j) {fractie aux=a[i];
a[i]=a[j];
a[j]=aux;
++i;--j;}
}while (i<=j);
if (i<ld) qsort(i,ld);
if (j>ls) qsort(ls,j);
}
int egal(fractie f,fractie g){
return (f.p==g.p && f.q==g.q);
}
int search(int ls,int ld,fractie f){
int mij;
while (ls<=ld){
mij=(ls+ld)/2;
if (egal(a[mij],f) && (!egal(a[mij-1],f))) return mij;
if (f.p*a[mij].q>f.q*a[mij].p) ls=mij+1;
else ld=mij-1;
}
return 0;
}
int main(){
int i,j,k;
fractie f;
freopen("trapez.in","r",stdin);
freopen("trapez.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i) scanf("%d %d",&v[i].x,&v[i].y);
for (i=1;i<n;++i)
for (j=i+1;j<=n;++j)
{a[++m].p=v[j].y-v[i].y;
a[m].q=v[j].x-v[i].x;
if (a[m].q<0){a[m].q=-a[m].q;
a[m].p=-a[m].p;}
simplifica(a[m]);
}
qsort(1,m);
for (i=1;i<n;++i)
for (j=i+1;j<=n;++j){
f.p=v[j].y-v[i].y;
f.q=v[j].x-v[i].x;
if (f.q<0){f.q=-f.q;
f.p=-f.p;}
simplifica(f);
k=search(1,m,f);
while (egal(f,a[k])) {++k;
++nr;}
--nr;
}
printf("%d",nr/2);
return 0;
}