Cod sursa(job #2876356)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 23 martie 2022 11:08:14
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda masonii Marime 1.79 kb
#include <bits/stdc++.h>

#define MAX_N 1000

using namespace std;

struct fractie {
    int x, y;

    bool operator < (const fractie &f) const {
        if ( y * f.y < 0 )
            return (long long)x * f.y > (long long)y * f.x;
        return (long long)x * f.y < (long long)y * f.x;
    }

    bool operator == (const fractie &f) const {
        return (long long)x * f.y == (long long)y * f.x;
    }
};

struct punct {
    int x, y;

    bool operator < (const punct &p) const {
        if ( x == p.x )
            return y < p.y;
        return x < p.x;
    }

    punct operator - (const punct &p) const {
        return { x - p.x, y - p.y };
    }
};

struct dreapta {
    punct a, b;

    fractie calctg() {
        int d;
        punct dif;

        dif = b - a;
        d = __gcd( dif.x, dif.y );
        if ( d == 0 )
            return { 0, 0 };
        return { dif.x / d, dif.y / d };
    }

    fractie tg = calctg();

    bool operator < (const dreapta &d) const {
        return tg < d.tg;
    }
};

punct v[MAX_N];
dreapta drepte[MAX_N * MAX_N];

signed main() {
    ifstream cin( "trapez.in" );
    ofstream cout( "trapez.out" );

    int n, nrDrepte, i, j;
    long long trapez;

    cin >> n;
    for ( i = 0; i < n; i++ )
        cin >> v[i].x >> v[i].y;

    sort( v, v + n );

    nrDrepte = 0;
    for ( i = 0; i < n; i++ ) {
        for ( j = i + 1; j < n; j++ )
            drepte[nrDrepte++] = { v[i], v[j] };
    }

    sort( drepte, drepte + nrDrepte );

    trapez = 0;
    i = j = 0;
    while ( i < nrDrepte ) {
        j = i;
        while ( j < nrDrepte && drepte[i].tg == drepte[j].tg ) {
            trapez += j - i;
            j++;
        }
        i = j;
    }

    cout << trapez;

    return 0;
}