Cod sursa(job #1814492)

Utilizator crazylamaRiclea Andrei crazylama Data 24 noiembrie 2016 08:40:11
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;

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

struct Punct {
    int x, y;
};

struct Dreapta {
    Punct A, B;
    double panta;
};

double AflaPanta(Dreapta D)
{
    if (D.B.x - D.A.x == 0)
        return 2 << 30;
    return (double)(D.B.y - D.A.y) / (double)(D.B.x - D.A.x);
}

void QuickSort(int st, int dr, vector<Dreapta> &v)
{
    if (st < dr)
    {
        int i = st, j = dr;
        Dreapta x = v[st];
        while (i < j)
        {
            while (i < j && v[j].panta >= x.panta)
                j--;
            v[i] = v[j];
            while (i < j && v[i].panta <= x.panta)
                i++;
            v[j] = v[i];
        }
        v[i] = x;
        QuickSort(st, i - 1, v);
        QuickSort(i + 1, dr, v);
    }
}

int main()
{
    int n, k = 0;
    f >> n;
    vector<Dreapta> v;
    vector<Punct> p;
    v.resize(n * (n - 1) / 2 + 1);
    p.resize(n);
    for (int i = 0; i < n; ++i)
        f >> p[i].x >> p[i].y;
    f.close();
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
        {
            v[k].A = p[i];
            v[k].B = p[j];
            v[k].panta = AflaPanta(v[k]);
            ++k;
        }
    int nr = 1;
    long long int sol = 0;
    QuickSort(0, k - 1, v);
    for (int i = 1; i < k; ++i)
    {
        if (v[i].panta == v[i - 1].panta)
                ++nr;
        else
        {
            sol += (nr * (nr - 1)) / 2;
            nr = 1;
        }
    }
    g << sol;
    g.close();
    return 0;
}