Cod sursa(job #1646739)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 10 martie 2016 17:30:45
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#define MAXN 1000
long long x[MAXN],y[MAXN],v1[MAXN*MAXN],v2[MAXN*MAXN];
inline void swap(int b,int e,long long *v){
    long long aux=v[b];
    v[b]=v[e];
    v[e]=aux;
}
void myqsort(int begin,int end){
    int b=begin,e=end;
    long long pivot1=v1[(b+e)/2],pivot2=v2[(b+e)/2];
    while(b<=e){
        while(v1[b]*pivot2<v2[b]*pivot1) b++;
        while(v1[e]*pivot2>v2[e]*pivot1) e--;
        if(b<=e){
            swap(b,e,v1);
            swap(b,e,v2);
            b++;e--;
        }
    }
    if(begin<e) myqsort(begin,e);
    if(b<end) myqsort(b,end);
}
int main(){
    FILE*fi,*fout;
    int i,n,con,m,j;
    fi=fopen("trapez.in" ,"r");
    fout=fopen("trapez.out" ,"w");
    fscanf(fi,"%d" ,&n);
    for(i=0;i<n;i++)
       fscanf(fi,"%lld%lld" ,&x[i],&y[i]);
    m=0;
    for(i=0;i<n-1;i++)
       for(j=i+1;j<n;j++){
          v1[m]=y[j]-y[i];
          v2[m]=x[j]-x[i];
          m++;
       }
    myqsort(0,m-1);
    i=0;
    con=0;
    while(i<m){
        j=i;
        while(j<m-1&&v1[j]*v2[j+1]==v1[j+1]*v2[j])
           j++;
        con=con+((j-i+1)*(j-i))/2;
        i=j+1;
    }
    fprintf(fout,"%d" ,con);
    fclose(fi);
    fclose(fout);
    return 0;
}