Cod sursa(job #2071563)

Utilizator biaiftimeIftime Bianca biaiftime Data 20 noiembrie 2017 19:42:40
Problema Trapez Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <stdlib.h>
#define Nmax 1002
#define Mmax 600002
FILE *f,*g;
typedef struct
{
    long long int a,b;
}fractie;
typedef struct
{
    long long int x,y;
}punct;
fractie panta[Mmax];
punct a[Nmax];
int n,k;
void Read(int *n,punct a[Nmax])
{
    int i;
    fscanf(f,"%d",n);
    for(i=1;i<=*n;++i)
    fscanf(f,"%lld %lld",&a[i].x,&a[i].y);
}
void Calcul(int n,punct a[Nmax],fractie panta[Mmax],int *k)
{
    int i,j;
    *k=-1;
    for(i=1;i<=n-1;++i)
    for(j=i+1;j<=n;++j)
    {
        ++*k;
        panta[*k].a=a[i].y-a[j].y;
        panta[*k].b=a[i].x-a[j].x;
    }
}
int Comp(const void *a,const void *b)
{
    fractie *pa=(fractie*)a;
    fractie *pb=(fractie*)b;
    if(pa->b==0)return -1;
    if(pb->b==0)return 1;
    if(pa->a*pb->b>pa->b*pb->a)return 1;
    if(pa->a*pb->b==pa->b*pb->a)return 0;
    return -1;
}
long long int Combinari(int x)
{
    return (x*(x-1))/2;
}
long long int Solve(int n,fractie panta[Mmax],int k)
{
    int i=0,nr=0,j;
    long long int nrfin=0;
    while(i<k)
    {
        nr=1;j=i+1;
        while(j<k&&panta[i].a*panta[j].b==panta[i].b*panta[j].a){++nr;++j;}
        if(nr!=1) nrfin=nrfin+Combinari(nr);
        i=j;
    }
    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,"%lld",Solve(n,panta,k));
    fclose(g);
    return 0;
}