Cod sursa(job #176688)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 11 aprilie 2008 16:00:10
Problema Trapez Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#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;
}