Cod sursa(job #937588)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 10 aprilie 2013 17:11:19
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <algorithm>
#include <fstream>
#include <map>
#include <vector>

using namespace std;

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;
    int slopeX = 0;
    vector<pair<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 if (points[i].second == points[j].second) {
                ++slopeX;
            } else {
                int num = (points[i].second - points[j].second);
                int denom = (points[i].first - points[j].first);
                int g = gcd(abs(num), abs(denom));
                num = num / g;
                denom = denom / g;
                if (denom < 0) {
                    denom = -denom;
                    num = -num;
                }

                slope.push_back(make_pair(num, denom));
            }
        }

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

    sort(slope.begin(), slope.end());

    vector<pair<int, int> >::iterator it;
    for (it = slope.begin(); it != slope.end(); ) {
        pair<int, int> val = *it;
        int cnt = 0;
        while (it != slope.end() && *it == val)
            ++cnt, ++it;

        result += cnt * (cnt - 1) / 2;
    }

    fout << result << endl;

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

    return 0;
}