Cod sursa(job #2916316)

Utilizator alin.gabrielAlin Gabriel Arhip alin.gabriel Data 29 iulie 2022 03:53:37
Problema Trapez Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define N 1000
#define NM 499500

struct point {
    int x, y;

    bool operator == (const point& a) const {
        return x == a.x && y == a.y;
    }
};

point v[N], m[NM];

//   a.x      b.x
//   ---  <   ---
//   a.y      b.y
bool cmp(point a, point b) {
    if (a.x == 0 || b.y == 0)
        return true;
    if (a.y == 0 || b.x == 0)
        return false;
    return a.x / (double)a.y < b.x / (double)b.y;
}

point slope(point a, point b) {
    int xd = b.x - a.x;
    int yd = b.y - a.y;
    int gcd = __gcd(yd, xd);
    if (gcd == 0)
        return {xd, yd};
    return {xd / gcd, yd / gcd};
}

int main() {
    int n, idx = 0;

    ifstream f("trapez.in");
    f >> n;
    for (int i = 0; i < n; i++) {
        f >> v[i].x >> v[i].y;
        for (int j = 0; j < i; j++)
                m[idx++] = slope(v[i], v[j]);
    }
    f.close();

    sort(m, m + idx, cmp);

    int s = 0, cnt = 1;
    for (int i = 0 ; i < idx; i++)
        if (m[i] == m[i + 1])
            cnt++;
        else {
            s += cnt * (cnt - 1);
            cnt = 1;
        }

    ofstream g("trapez.out");
    g << (s >> 1);
    g.close();
    return 0;
}