Cod sursa(job #1542629)

Utilizator Julian.FMI Caluian Iulian Julian. Data 5 decembrie 2015 15:26:00
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("trapez.in");
ofstream fout("trapez.out");
struct pumct{long x,y;}p[1003];
struct pante{long a,b;}v[500000],aux;

void sortare(long st,long dr)
{long i,j;
i=st;j=dr;aux=v[st];
while(i<j)
{while(i<j && aux.a*v[j].b<=v[j].a*aux.b)j--;
v[i]=v[j];
while (i<j && v[i].a*aux.b<=v[i].b*aux.a)i++;
v[j]=v[i];
}

v[i]=aux;
if(st+1<i)sortare(st,i-1);
if(i+1<dr)sortare(i+1,dr);
}

void redu(long &a,long &b)
{
long r,aux,aub;
aux=a;aub=b;
while(aub)
{r=aux%aub;
aux=aub;aub=r;
}
a=a/aux;
b=b/aux;

}


int main()
{long i,n,j,nr=0,cont;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>p[i].x>>p[i].y;

    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
    {v[++nr].a=p[j].y-p[i].y;
     v[nr].b=p[j].x-p[i].x;
    }
    for(i=1;i<=nr;i++){redu(v[i].a,v[i].b);}
    sortare(1,nr);
cont=0;
long a;i=1;
    while(i<=nr)
    {a=1;
    while(v[i].a==v[i+1].a && v[i].b==v[i+1].b){a++;i++;}
    cont+=a*(a-1)/2;
    i++;
    }
fout<<cont;
}