Cod sursa(job #1427916)

Utilizator OviTzu24Carabian Ovidiu OviTzu24 Data 3 mai 2015 12:32:22
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#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;
}