Cod sursa(job #2176173)

Utilizator Marina23Oprea Marina Marina23 Data 16 martie 2018 21:23:45
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <math.h>
#include <algorithm>

using namespace std;

struct punct{long long int X;long long int Y;} Pct[1200];
struct perechi{long long int A;long long int B;} Panta[1200];

long long int N,i,j,A,B,Nrpante,Cmmdc,Nr,Raspuns;

long long int cmmdc(long long int A,long long int B)
{
    long long int R;

    while(B!=0) {R=A%B; A=B; B=R;}
    return A;
}

bool ordonare(perechi X,perechi Y)
{
    if(X.A<Y.A) return 1;
    if(X.A==Y.A and X.B<Y.B) return 1;
    return 0;
}

int main()
{
    ifstream fin("trapez.in");
    ofstream fout("trapez.out");

    fin>>N;
    for(i=1;i<=N;++i) fin>>Pct[i].X>>Pct[i].Y;
    for(i=1;i<=N;++i)
        for(j=i+1;j<=N;++j)
        {
            A=Pct[j].Y-Pct[i].Y;
            B=Pct[i].X-Pct[j].X;
            if(A<0) {A=-A; B=-B;}
            if(B!=0)
            {
                Cmmdc=cmmdc(fabs(A),fabs(B));
                A/=Cmmdc; B/=Cmmdc;
                ++Nrpante;
                Panta[Nrpante].A=A;
                Panta[Nrpante].B=B;
            }//if B
            else
            {
                ++Nrpante;
                Panta[Nrpante].A=0;
                Panta[Nrpante].B=0;
            }
        }
    stable_sort(Panta+1,Panta+Nrpante+1,ordonare);
    i=1;
    while(i<=Nrpante)
    {
        Nr=1; j=i+1;
        while(j<=Nrpante and Panta[j].A==Panta[i].A and Panta[j].B==Panta[i].B) {++j; ++Nr;}
        i=j;
        Raspuns+=(Nr-1)*Nr/2;
    }
    fout<<Raspuns;

    fin.close ();
    fout.close();
    return 0;
}