Cod sursa(job #2876335)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 23 martie 2022 10:54:42
Problema Trapez Scor 40
Compilator cpp-64 Status done
Runda masonii Marime 1.66 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;
    }
};

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 tg() {
        int d;
        punct dif;

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

punct v[MAX_N];
map <fractie, int> tang;
map <punct, int> pct;

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

    int n, i, j;
    long long trapez;
    dreapta d;

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

    sort( v, v + n );

    trapez = 0;
    for ( i = 0; i < n; i++ ) {
        for ( j = i + 1; j < n; j++ ) {
            d = { v[i], v[j] };
            trapez += tang[d.tg()];
            tang[d.tg()]++;
        }
    }

    for ( i = 0; i < n; i++ )
        pct[v[i]] = 1;
    for ( i = 0; i < n; i++ ) {
        for ( j = i + 1; j < n; j++ ) {
            if ( v[i].x < v[j].x && v[i].y < v[j].y )
                trapez -= pct[ { v[i].x, v[j].y }] * pct[ { v[j].x, v[i].y }];
        }
    }

    cout << trapez;

    return 0;
}