Cod sursa(job #2844725)

Utilizator AlexNicuNicu Alexandru AlexNicu Data 5 februarie 2022 11:07:55
Problema Trapez Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define NMAX 1001

#define EPS 0.0001

struct DREAPTA {
    double panta, origine;
    bool operator < ( const DREAPTA& other ) const {
        if ( panta == other.panta )
            return origine < other.origine;
        return panta < other.panta;
    }
};

struct POINT {
    double x, y;
};

vector<DREAPTA> drepte;

vector<double> same_x;
vector<double> same_y;

POINT v[NMAX];

int main() {
    int n, i, j, ans, cnt;
    double p, origin;
    cin >> n;
    for ( i = 0; i < n; i++ ) {
        cin >> v[i].x >> v[i].y;
    }
    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) {
                p = (v[i].y - v[j].y) / (v[i].x - v[j].x);
                origin = v[i].y - p * v[i].x;
                drepte.push_back({p, origin});
            }
        }
    }
    sort ( drepte.begin(), drepte.end() );
    ans = cnt = 0;
    for ( i = 1; i < drepte.size(); i++ ) {
        cnt = 1;
        while ( i < drepte.size() && drepte[i].panta - drepte[i - 1].panta < EPS ) {
            i++;
            cnt++;
        }
        ans += cnt * ( cnt - 1 ) / 2;
    }
    for ( i = 0; i < n; i++ ) {
        for ( j = i + 1; j < n; j++ ) {
            if ( v[i].x == v[j].x )
                same_x.push_back(v[i].x);
            if ( v[i].y == v[j].y )
                same_y.push_back(v[i].y);
        }
    }
    ans += ( same_x.size() ) * ( same_x.size() - 1 ) / 2;
    ans += ( same_y.size() ) * ( same_y.size() - 1 ) / 2;
    cout << ans;
    return 0;
}