Cod sursa(job #2082750)

Utilizator anca.sotirAnca Sotir anca.sotir Data 6 decembrie 2017 19:14:43
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("trapez.in");
ofstream g("trapez.out");
struct fractie{
    int numarator,numitor;
};
struct punct{
    int x,y;
};
fractie p[502000];
punct v[1002];

int n,k=0;

int cmmdc(int a,int b)
{
    if(b==0) return a;
    int r=a%b;
    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

fractie panta(punct a, punct b)
{
    fractie p;
    p.numarator=b.y-a.y;
    p.numitor=b.x-a.x;
    int c=cmmdc(p.numarator,p.numitor);
    p.numarator/=c;
    p.numitor/=c;
    if((p.numitor<0 && p.numarator<0) || (p.numitor<0 && p.numarator>0))
    {
        p.numarator=-p.numarator;
        p.numitor=-p.numitor;
    }
    return p;
}
///?????
bool comparare(fractie i,fractie j)
{
    if(i.numarator*j.numitor-i.numitor*j.numarator<0)
        return true;
    return false;
}

int main()
{
    int nrTrapez=0;
    f>>n;
    for(int i=1;i<=n;++i)
        f>>v[i].x>>v[i].y;
    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j)
            p[++k]=panta(v[i],v[j]);
    sort(p+1,p+k+1,comparare);
    int lungime=1;
    for(int i=2;i<=k;++i)
    {
        if(p[i].numitor==p[i-1].numitor && p[i].numarator==p[i-1].numarator)
            ++lungime;
        else
        {
            nrTrapez+=((lungime-1)*lungime/2); ///combinari de lungime luate cate 2 trapeze
            lungime=1;
        }
    }
    nrTrapez+=((lungime-1)*lungime/2);
    g<<nrTrapez;
    return 0;
}