Cod sursa(job #2083306)

Utilizator biaiftimeIftime Bianca biaiftime Data 7 decembrie 2017 15:20:51
Problema Trapez Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <stdio.h>
#include <stdlib.h>
#define Nmax 1004
#define Mmax 1000002
FILE *f,*g;
typedef struct
{
    int a,b;
}fractie;
typedef struct
{
    int x,y;
}punct;
fractie panta[Mmax];
punct a[Nmax];
int n,k,nrpant0;
void Read(int *n,punct a[Nmax])
{
    int i;
    fscanf(f,"%d",n);
    for(i=1;i<=*n;++i)
    fscanf(f,"%d %d",&a[i].x,&a[i].y);
}
int Cmmdc(int x,int y)
{
    int r;
    while(y!=0)
    {
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}
void Calcul(int n,punct a[Nmax],fractie panta[Mmax],int *k)
{
    int i,j,val;
    *k=-1;
    for(i=1;i<=n-1;++i)
    for(j=i+1;j<=n;++j)
    {
        if(a[i].x-a[j].x==0)nrpant0++;
        else{
        ++*k;
        panta[*k].a=a[i].y-a[j].y;
        panta[*k].b=a[i].x-a[j].x;
        if(panta[*k].b<0){
            panta[*k].a*=-1;
            panta[*k].b*=-1;
        }
        val=Cmmdc(abs(panta[*k].a),abs(panta[*k].b));
        panta[*k].a/=val;
        panta[*k].b/=val;
        /*if(panta[*k].a<0&&panta[*k].b<0)
        {
            panta[*k].a*=-1;
            panta[*k].b*=-1;
        }
        else if(panta[*k].a>0&&panta[*k].b<0)
        {
            panta[*k].a*=-1;
            panta[*k].b*=-1;
        }*/
        }
    }
}
int Comp(const void *a,const void *b)
{
    fractie *pa=(fractie*)a;
    fractie *pb=(fractie*)b;
    if(pa->a*pb->b>pa->b*pb->a)return 1;
    return -1;
}
int Solve(int n,fractie panta[Mmax],int k)
{
    int i,nr=1;
    int nrfin=0;
    for(i=1;i<k;++i)
    if(panta[i].a==panta[i-1].a&&panta[i].b==panta[i-1].b)nr++;
    else {nrfin=nrfin+nr*(nr-1)/2; nr=1;}
    if(nr!=1)nrfin=nrfin+nr*(nr-1)/2;
    return nrfin;
}
int main()
{
    f=fopen("trapez.in","r");
    g=fopen("trapez.out","w");
    Read(&n,a);
    fclose(f);
    Calcul(n,a,panta,&k);
    ++k;
    qsort(panta,k,sizeof(fractie),Comp);
    fprintf(g,"%d",Solve(n,panta,k)+nrpant0*(nrpant0-1)/2);
    fclose(g);
    return 0;
}