Cod sursa(job #2453543)

Utilizator ZanoxNonea Victor Zanox Data 4 septembrie 2019 13:18:01
Problema Trapez Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <iostream>
#include <string>
#include <unordered_map>
#include <fstream>
#include <vector>

using namespace std;

#define x first
#define y second

inline int abs(int x) {
    return ((x > 0) ? x : -x);
}

int gcd(int x, int y) {
    while (x != 0 && y != 0) {
        if (abs(x) > abs(y)) x %= y;
        else y %= x;
    }

    if (x == 0) return y;
    return x;
}

struct Fraction {
    int num, den;

    Fraction(int x, int y) {
        if (y == 0) {
            num = 1;


            den = 0;
            return;
        }

        if (x == 0) {
            num = 0;

            den = 1;
            return;
        }

        int d = gcd(x, y);

        num = x / d;
        den = y / d;

        if (num < 0) {
            num *= -1;
            den *= -1;
        }
    }

    string toString() const {
        return string() + to_string(num) + " / " + to_string(den);
    }

    bool operator< (const Fraction& f) const {
        if (f.num > num) return true;
        return f.den > den;
    }

    bool operator== (const Fraction& f) const {
        return num == f.num && den == f.den;
    }
};


ifstream fin("trapez.in");
ofstream fout("trapez.out");

namespace std {
        template<> struct hash<Fraction> {
        size_t operator() (const Fraction& f) const {
            return hash<int>()(f.num) ^ hash<int>()(f.den);
        }
    };
}

int main() {
    vector<pair<int, int>> v;
    int n;

    fin>>n;

    for (int i = 0; i < n; i++) {
        int x, y;
        fin>>x>>y;

        v.push_back(make_pair(x, y));
    }

    unordered_map<Fraction, int> freqMap;

    for (int i = 0; i < n-1; i++)
    for (int j = i + 1; j < n; j++) {
        int x = v[i].x - v[j].x;
        int y = v[i].y - v[j].y;

        Fraction f = Fraction(x, y);

        unordered_map<Fraction, int>::iterator it = freqMap.find(f);

        if (it == freqMap.end()) {
            freqMap[f] = 1;
        } else {
            it->second ++;
        }
    }

    int64_t sol = 0;

    for (auto p : freqMap) {
        //cout<<p.x.toString()<<" -> "<<p.y<<'\n';
        int count = p.y;
        sol += (int64_t) count * (count - 1) / 2;
    }

    fout<<sol;
}