Cod sursa(job #2083113)

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

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

struct punct{
    int x,y;
};

struct fractie{
    int nrt,num;
};

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 frc;

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


    int c=cmmdc(frc.nrt,frc.num);
    frc.nrt/=c;
    frc.num/=c;

    return frc;
}

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;
    int a,b;
    vector<punct>v;
    vector<fractie>frc;
    for(int i=0;i<n;++i){
        f>>a>>b;v.push_back({a,b});
    }
    for(int i=0;i<n-1;++i)
        for(int j=i+1;j<n;++j)
            frc.push_back(panta(v[i],v[j]));

        sort(frc.begin(),frc.end(),compar);

        int lungime=1;

    for(int i=1;i<frc.size();++i){
        if((frc[i].num==frc[i-1].num)&&(frc[i].nrt==frc[i-1].nrt)) ++lungime;
        else {
            nr+=((lungime-1)*lungime/2); ///combinari de lungime luate cate 2 trapeze
            lungime=1;
        }
    }
    nr+=((lungime-1)*lungime/2);
    g<<nr;
    return 0;
}