Pagini recente » Cod sursa (job #2628481) | Cod sursa (job #1267821) | Cod sursa (job #1708988) | Cod sursa (job #269532) | Cod sursa (job #176785)
Cod sursa(job #176785)
#include <cstdio>
typedef struct Tfractie{
int p,q;}fractie;
typedef struct Tpunct{
int x,y;}punct;
punct v[1001];
fractie a[600001];
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 main(){
int i,j;
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<=m;i++) printf("%d %d\n",a[i].p,a[i].q);
for (nr=0,i=1;i<m;)
if (egal(a[i],a[i+1])){
j=0;
while (egal(a[i],a[i+1]) && i<m) {++j;++i;}
++i;
nr+=j*(j+1)/2;}
else i++;
printf("%d",nr);
return 0;
}