Cod sursa(job #3185751)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 20 decembrie 2023 10:18:26
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int Nmax = 1000;

struct punct{
    long long x, y;
};

struct fractie{
    long long numarator, numitor;
};

bool cmp(fractie a, fractie b){
    return a.numarator * b.numitor < b.numarator * a.numitor;
}

punct v[Nmax];
fractie pante[Nmax * Nmax];

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

    int n, len, sol, cnt, cmmdc, paralele_Ox, paralele_Oy;

    fin >> n;
    for(int i = 0; i < n; i++){
        fin >> v[i].x >> v[i].y;
    }

    len = 0;
    paralele_Ox = 0;
    paralele_Oy = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(v[j].y - v[i].y == 0){
                paralele_Ox++;
            }
            else if(v[j].x - v[i].x == 0){
                paralele_Oy++;
            }
            else{
                pante[len].numarator = (v[j].y - v[i].y);
                pante[len].numitor = (v[j].x - v[i].x);

                cmmdc = __gcd(pante[len].numarator, pante[len].numitor);
                pante[len].numarator /= cmmdc;
                pante[len].numitor /= cmmdc;

                len++;
            }
        }
    }

    sort(pante, pante + len, cmp);

    sol = paralele_Ox * (paralele_Ox - 1) / 2;
    sol += paralele_Oy * (paralele_Oy - 1) / 2;

    cnt = 1;
    for(int i = 1; i < len; i++){
        if(pante[i - 1].numarator * pante[i].numitor == pante[i].numarator * pante[i - 1].numitor){
            cnt++;
        }
        else{
            if(cnt >= 2){
                sol += cnt * (cnt - 1) / 2;
            }
            cnt = 1;
        }
    }

    fout << sol;

    return 0;
}