Cod sursa(job #932339)

Utilizator sebii_cSebastian Claici sebii_c Data 28 martie 2013 20:54:46
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <algorithm>
#include <fstream>
#include <map>
#include <vector>

using namespace std;

const double EPS = 1e-6;

struct comp {
    bool operator() (const double& lhs, const double& rhs) {
        return lhs < rhs + EPS; 
    }
};

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

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

    int N;
    fin >> N;

    vector<pair<int, int> > points;
    for (int i = 0; i < N; ++i) {
        int x, y;
        fin >> x >> y;
        points.push_back(make_pair(x, y));
    }

    int slopeY = 0;
    map<pair<int, int>, int> slope;
    for (int i = 0; i < N; ++i)
        for (int j = i + 1; j < N; ++j) {
            if (points[i].first == points[j].first) {
                ++slopeY;
            } else {
                pair<int, int> s;
                int num = (points[i].second - points[j].second);
                int denom = (points[i].first - points[j].first);
                if (num == 0) {
                    ++slope[make_pair(0, 0)];
                    continue;
                }

                int g = gcd(abs(points[i].first - points[j].first), 
                        abs(points[i].second - points[j].second));
                num = num / g;
                denom = denom / g;
                ++slope[make_pair(num, denom)];
            }
        }

    long long result = 0;
    result += slopeY * (slopeY - 1) / 2;

    map<pair<int, int>, int>::iterator it;
    for (it = slope.begin(); it != slope.end(); ++it) {
        int c = it->second;
        result += c * (c - 1) / 2;
    }

    fout << result << endl;

    fin.close();
    fout.close();

    return 0;
}