Cod sursa(job #2083114)

Utilizator VoineaAndreiVoinea Ioan-Andrei VoineaAndrei Data 7 decembrie 2017 03:44:47
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<bits/stdc++.h>
using namespace std;

ifstream f("trapez.in");
ofstream g("trapez.out");

//struct de puncte
struct punct{
    int x,y;
};

//struct de fractii
struct fractie{
    int nrt,num;
};

//algoritmul lui euclid
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;
}

//functie care calculeaza panta
fractie panta(punct a,punct b){

    fractie frc;

    frc.nrt=b.y-a.y;
    frc.num=b.x-a.x;

    //impartim la cmmdc ca sa simplificam fractia
    int c=cmmdc(frc.nrt,frc.num);
    frc.nrt/=c;
    frc.num/=c;

    return frc;
}

//functia care compara doua fractii
bool compar(fractie a,fractie b){
    if(a.nrt<0 && a.num>0){
        if((b.num>0&&b.nrt>0)||(b.num<0&&b.nrt<0)) return false;
        else {
            if(a.nrt*b.num-a.num*b.nrt<0) return false;
            return true;
        }
    }
    if(b.nrt<0 && b.num>0){
        if((a.num>0&&a.nrt>0)||(a.num<0&&a.nrt<0)) return true;
        else {
            if(a.nrt*b.num-a.num*b.nrt<0) return false;
            return true;
        }
    }

    if(a.nrt*b.num-a.num*b.nrt<0)return true;
    return false;

}

int main(){

    int n,nr=0;
    f>>n;

    //vector de puncte
    vector<punct>v;

    //vector de fractii
    vector<fractie>frc;

    //citire
    int a,b;
    for(int i=0;i<n;++i){
        f>>a>>b;v.push_back({a,b});
    }

    //calculam pantele si le punem in vectorul de fractii
    for(int i=0;i<n-1;++i)
        for(int j=i+1;j<n;++j)
            frc.push_back(panta(v[i],v[j]));

        //sortam vectorul
        sort(frc.begin(),frc.end(),compar);


        //calculam numarul de trapeze ce se pot forma
    int L=1;
    for(int i=1;i<frc.size();++i){
        if((frc[i].num==frc[i-1].num)&&(frc[i].nrt==frc[i-1].nrt)) ++L;
        else {
            nr+=((L-1)*L/2); //combinari de L luate cate 2
            L=1;
    }
}
        nr+=((L-1)*L/2);


    g<<nr;
}