Cod sursa(job #2607455)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 29 aprilie 2020 19:33:38
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    a = abs(a), b = abs(b);
    while (a)
        swap(a, b %= a);
    return b;
}

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

    int n;
    in >> n;

    vector <pair <int, int>> coord(n);
    for (auto & i : coord)
        in >> i.first >> i.second;

    vector <pair <int, int>> pante;
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dx = coord[j].first - coord[i].first;
            int dy = coord[j].second - coord[i].second;
            int g = gcd(dx, dy);
            dx /= g, dy /= g;
            if (dx < 0)
                dx = -dx, dy = -dy;

            pante.push_back({ dx, dy });
        }
    }

    sort(pante.begin(), pante.end());

    for (int i = 0; i < (int)pante.size(); i++) {
        int nr = 1;
        while (i + 1 < (int)pante.size() && pante[i + 1] == pante[i])
            nr++, i++;
        ans += 1LL * nr * (nr - 1) / 2;
    }

    out << ans << '\n';

    return 0;
}