Cod sursa(job #2456722)

Utilizator mircearoataMircea Roata Palade mircearoata Data 15 septembrie 2019 12:44:57
Problema Trapez Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#pragma GCC optimize("O3")

#include <iostream>
#include <fstream>
#include <unordered_map>

using namespace std;

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

int cmmdc(int a, int b)
{
    if(b == 0)
        return a;
    while(b)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

struct fractie
{
    int a;
    int b;

    fractie(int a, int b)
    {
        this->a = a;
        this->b = b;
        simplifica();
        if(this->b < 0)
        {
            this->a = -(this->a);
            this->b = -(this->b);
        }
    }

    void simplifica()
    {
        int c = cmmdc(a, b);
        a /= c;
        b /= c;
    }
};

namespace std{
template<>
struct hash<fractie>
{
    size_t operator()(const fractie& f) const
    {
        return (f.a ^ (f.b << 1));
    }
};
}

ostream & operator<< (ostream & os, fractie & f)
{
    os << f.a << ' ' << f.b;
    return os;
}

bool operator<(const fractie f1, const fractie f2)
{
    return f1.a * f2.b < f1.b * f2.a;
}

bool operator==(const fractie f1, const fractie f2)
{
    return f1.a * f2.b == f1.b * f2.a;
}

struct punct
{
    int x, y;
};

istream & operator>> (istream & is, punct & p)
{
    is >> p.x >> p.y;
    return is;
}

fractie panta(punct a, punct b)
{
    fractie f = fractie(a.y - b.y, a.x - b.x);
    return f;
}

unordered_map<fractie, int> cnt;

int n;
punct v[1000];
unsigned long long ans;

int main()
{
    in >> n;
    for(int i = 0; i < n; i++)
        in >> v[i];
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            cnt[panta(v[i], v[j])]++;
    for(pair<fractie, int> paralele : cnt)
        ans += 1LL * paralele.second * (paralele.second - 1) / 2;
    out << ans;
    return 0;
}