Cod sursa(job #2453534)

Utilizator ZanoxNonea Victor Zanox Data 4 septembrie 2019 12:38:04
Problema Trapez Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <string>
#include <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;
        }

        int d = gcd(x, y); //is gcd neg if x and y are neg?

        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;
    }
};


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


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));
    }

    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);

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

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

    int sol = 0;

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

    fout<<sol;
}