Cod sursa(job #2608540)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 1 mai 2020 14:34:52
Problema Trapez Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <utility>
#include <unordered_map>
#include <map>

using namespace std;

typedef long long LL;

struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};

int GCD(LL a, LL b)
{
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }

    return a;
}

int main()
{
    int n;
    ifstream fin("trapez.in");
    fin >> n;
    pair<LL, LL>* coords = new pair<LL, LL>[n];
    for (int i = 0; i < n; i++)
    {
        pair<LL, LL> crt;
        fin >> crt.first >> crt.second;
        coords[i] = crt;
    }
    fin.close();

    unordered_map<pair<LL, LL>, LL, hash_pair> vectors;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            LL dx = coords[i].first - coords[j].first;
            LL dy = coords[i].second - coords[j].second;

            LL l = GCD(abs(dx), abs(dy));
            dx /= l;
            dy /= l;

            if (dx == 0)
            {
                if (dy < 0)
                    dy = -dy;
            }
            else
                if (dx < 0)
                {
                    dx = -dx;
                    dy = -dy;
                }

            pair<LL, LL> vec = make_pair(dx, dy);

            if (vectors.find(vec) == vectors.end())
                vectors[vec] = 0;

            vectors[vec]++;
        }
    }

    delete[] coords;
    coords = NULL;

    LL result = 0;
    for (auto cnt : vectors)
        result += cnt.second * (cnt.second - 1) / 2;

    ofstream fout("trapez.out");
    fout << result;
    fout.close();

    return 0;
}